Competition problem — Number theory

Library / /11 of 22

Number theory Difficulty 5.5 AIME, harder Prove it Ukraine

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

Solution

To the contrary, assume that $T(ab + cd) \le 2$ .

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

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.