Olympiad Maths Prep

Library / /29 of 60

Number theory Difficulty 5.9 AIME, harder Prove it Ukraine

We know that a certain number AA has exactly 2018 positive integer factors (including 1 and number AA itself), and it is divisible by 2018. Prove that AA is not divisible by 201822018^2.

Solution

Let A=p1k1p2k2pnknA = p_1^{k_1} p_2^{k_2} \dots p_n^{k_n} be a canonical prime factorization of AA, where pip_i are different prime factors, and kik_i are positive integers, i=1,ni = 1, n. Knowing the total number of positive integer factors of AA we can conclude that
(k1+1)(k2+1)(kn+1)=2018. (k_1 + 1)(k_2 + 1)\dots(k_n + 1) = 2018.

Since the left-hand side comprises factors each of which is greater or equal to 2, we have only two cases:

1) k1+1=2018k_1 + 1 = 2018.
2) (k1+1)(k2+1)=21009(k_1 + 1)(k_2 + 1) = 2 \cdot 1009.

From the first case, AA has a canonical prime factorization of the form: A=p12017A = p_1^{2017}, which contradicts the fact that A2018A \neq 2018, since in that case AA can't be divisible by both 2 and the prime number 1009.

Hence, (k1+1)(k2+1)=21009(k_1 + 1)(k_2 + 1) = 2 \cdot 1009, which yields, without loss of generality, k1=1k_1 = 1, k2=1008k_2 = 1008. Therefore, A=p1p21008A = p_1 p_2^{1008}, moreover from divisibility by 2 and 1009 we obtain A=210091008A = 2 \cdot 1009^{1008} or A=100921008A = 1009 \cdot 2^{1008}. However, none of these numbers is divisible by 201822018^2, Q.E.D.

Looking for a route rather than 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.