## Thursday, October 12, 2006

### Divvy It Up. Topic: Number Theory. Level: AMC.

Problem: Find the number of divisors of a postive integers.

Solution: For all you people at math club who didn't understand it... here it is. Suppose our number is $n = p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k}$, where the $p$'s are the prime divisors of $n$ and the $e$'s are the number of times (power) each $p$ divides $n$. For example, $36 = 2^2 \cdot 3^2$.

We will show that the number of divisors is $(e_1+1)(e_2+1) \cdots (e_k+1)$. Let $d$ be a divisor of $n$. Write $d$ as

$d = p_1^{a_1} \cdot p_2^{a_2} \cdots p_k^{a_k}$.

We know that $d$ can only have the prime divisors of $n$ or it obviously won't divide $n$. So now it remains to choose the $a$'s. Well, what can $a_1$ be? It can be $0, 1, 2, \ldots, e_1$ but if $a_1 > e_1$ then $d$ will have more $p_1$'s than $n$ and won't divide it. So there are $e_1+1$ choices there. Similarly, $a_2$ can be $0, 1, 2, \ldots, e_2$ and $a_j$ can be $0, 1, 2, \ldots, e_j$ for $j = 3, 4, \ldots, k$.

So if we just multiply the number of ways we can pick the power on each prime factor, we get the total number of divisors, i.e. $(e_1+1)(e_2+1) \cdots (e_k+1)$. QED.

--------------------

Comment: This is very important for general number theory; it is one of the fundamental ideas. Plus, it's logical and easy to remember so it should always be accessible during competitions.

--------------------

Practice Problem: (2002-2003 MIC Championships Team Test - #2) How many natural numbers less than $50,000$ have exactly $35$ positive integer factors?

1. WOW THAT"S SOO COOL~
so 36 has (2+1)(2+1)=9 factors!
35... mm.. so 5*7=35... and (2^5)(2^7) is.. uh.. 4096
(3^5)(2^7)=30014
(2^7)(3^5)=69984

So 2 numbers?

but how am i supposed to do this with out a calc??

2. the powers are one less than the factors; those should be 4 and 6, not 5 and 7.

calculating powers without a calculator isn't so hard, xuan :)

3. also, the primes have to be different. (2^5) (2^7) counts as 2^12, which has 13 factors.

4. .. oh yea. 4 and 6.. right....
cool cool thanks tOrajirOu