51st Ukrainian National Mathematical Olympiad, 4th Round

Question

For the natural number N = p_1^a_1 p_2^a_2 p_n^a_n, written in the canonical form (p_i are distinct primes and a_i are naturals, 1 i n), we denote T(N) = a_1 + a_2 + + a_n. For some distinct natural a, b, c, d the number ab + cd is divisible by ac + bd. Prove that T(ab + cd) 3.

Accepted Answer

To the contrary, assume that T(ab + cd) 2. Problem 8-3 implies that T(ac + bd) 2. Now, since (ac + bd) (ab + cd), we have that T(ab + cd) T(ac + bd) 2, which by the assumption means that T(ab + cd) = T(ac + bd) = 2. But then (ac + bd) = (ab + cd) (a - d)(b - c) = 0, which is a contradiction to the fact that our numbers are distinct.