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?

4 comments:

  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??

    ReplyDelete
  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 :)

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

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

    ReplyDelete