Maths Olympiad Prep

Library / /7 of 15

Number theory Difficulty 5.3 AIME, harder Prove it Estonia

How many positive integers are there that are divisible by 20102010 and that have exactly 20102010 divisors (1 and the integer itself included)?

Solution

Let NN be a positive integer that is divisible by 20102010 and that has exactly 20102010 positive divisors. Since 2010=235672010 = 2 \cdot 3 \cdot 5 \cdot 67, also NN should be divisible by these four primes. Thus, N=2a3b5c67dsN = 2^a \cdot 3^b \cdot 5^c \cdot 67^d \cdot s, where a,b,c,d>0a, b, c, d > 0 and ss is not divisible by any of the primes 2,3,5,672, 3, 5, 67. All the factors of NN can be expressed as 2i3j5k67lt2^i \cdot 3^j \cdot 5^k \cdot 67^l \cdot t, where 0ia,0jb,0kc,0ld0 \le i \le a, 0 \le j \le b, 0 \le k \le c, 0 \le l \le d, and tt is a factor of ss. There are a+1a+1 choices for ii (from 00 to aa) and similarly, there are b+1,c+1b+1, c+1 and d+1d+1 choices for j,kj, k and ll, respectively. Therefore, NN has δ(N)=(a+1)(b+1)(c+1)(d+1)δ(s)\delta(N) = (a+1)(b+1)(c+1)(d+1)\delta(s) different factors, where δ(x)\delta(x) stands for the number of factors of xx. We require δ(N)=2010\delta(N) = 2010. As a+1>1,b+1>1,c+1>1a+1 > 1, b+1 > 1, c+1 > 1, and d+1>1d+1 > 1, we see that each of these numbers is divisible by some prime numbers and the number δ(N)=(a+1)(b+1)(c+1)(d+1)δ(s)\delta(N) = (a+1)(b+1)(c+1)(d+1)\delta(s) can thus be expressed as a product of at least four prime numbers. But as 20102010 itself is a product of exactly four prime numbers, we conclude that a+1,b+1,c+1a+1, b+1, c+1, and d+1d+1 are exactly those primes 2,3,52, 3, 5, and 6767, in some order, and δ(s)=1\delta(s) = 1. From the latter condition we see that s=1s=1 because any numbers bigger than 11 has more than one factor. So for NN to satisfy the conditions, NN must be expressible as 2a3b5c67d2^a \cdot 3^b \cdot 5^c \cdot 67^d, where a,b,c,da, b, c, d are the numbers 1,2,41, 2, 4, and 6666 in some order. Thus there are 4!=244! = 24 numbers satisfying the conditions.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.