Maths Olympiad Prep

Library / /27 of 133

Number theory Difficulty 5.1 AIME, harder Prove it Saudi Arabia

Prove that among any nine divisors of 30201030^{2010} there are two whose product is a perfect square.

Solution

Let us factor 302010=22010320105201030^{2010} = 2^{2010} \cdot 3^{2010} \cdot 5^{2010}.

Any divisor dd of 30201030^{2010} can be written as d=2a3b5cd = 2^a 3^b 5^c where 0a,b,c20100 \leq a, b, c \leq 2010.

The product of two divisors d1=2a13b15c1d_1 = 2^{a_1} 3^{b_1} 5^{c_1} and d2=2a23b25c2d_2 = 2^{a_2} 3^{b_2} 5^{c_2} is a perfect square if and only if a1+a2a_1 + a_2, b1+b2b_1 + b_2, and c1+c2c_1 + c_2 are all even.

This is equivalent to a1a2(mod2)a_1 \equiv a_2 \pmod{2}, b1b2(mod2)b_1 \equiv b_2 \pmod{2}, c1c2(mod2)c_1 \equiv c_2 \pmod{2}.

Thus, for each divisor, consider the triple (amod2,bmod2,cmod2)(a \bmod 2, b \bmod 2, c \bmod 2). There are 2×2×2=82 \times 2 \times 2 = 8 possible such triples.

If we select 9 divisors, by the pigeonhole principle, at least two of them must have the same triple. For these two divisors, the exponents of 22, 33, and 55 have the same parity, so their sum is even for each prime, and thus their product is a perfect square.

Therefore, among any nine divisors of 30201030^{2010}, there are two whose product is a perfect square.

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.