Maths Olympiad Prep

Library / /2 of 36

Number theory Difficulty 5.2 AIME, harder Prove it Italy

Problem:

Prove that there exist infinitely many positive integers mm such that the number of distinct odd prime factors of m(m+3)m(m+3) is a multiple of 3.

Solution

Solution:

Let us call f(m)=m(m+3)f(m)=m(m+3), and d(m)d(m) the number of distinct odd prime factors of f(m)f(m). We have that f(m)f(m+1)=f(m2+4m)f(m) f(m+1)=f\left(m^{2}+4 m\right); moreover, f(m)f(m) and f(m+1)f(m+1) have 2 as their only common prime factor. Indeed, suppose that pp is an odd prime dividing both f(m)f(m) and f(m+1)f(m+1). Then pp also divides f(m+1)f(m)=2(m+2)f(m+1)-f(m)=2(m+2), and hence pp divides m+2m+2. But m+2m+2 and m+3m+3 are coprime, so pp divides both mm and m+2m+2, and we have thus reached a contradiction. It follows that d(m2+4m)=d(m)+d(m+1)d\left(m^{2}+4 m\right)=d(m)+d(m+1).

Finally, observe that, if the remainders of d(n)d(n) and d(n+1)d(n+1) upon division by 3 are distinct and both different from 0, then d(n2+4n)=d(n)+d(n+1)d\left(n^{2}+4 n\right)=d(n)+d(n+1) is divisible by 3.

We want to show that, for any fixed integer n>2n>2, there exists an integer mnm \geq n such that d(m)d(m) is divisible by 3.

We proceed by contradiction: assume that d(m)d(m) is not a multiple of 3 for every mnm \geq n. Then, for every mnm \geq n, the remainder of d(m)d(m) upon division by 3 must equal the remainder of d(m+1)d(m+1), otherwise d(m2+4m)=d(m)+d(m+1)d\left(m^{2}+4 m\right)=d(m)+d(m+1) would be a multiple of 3. It follows that d(m)d(m) always has the same remainder for every mnm \geq n. This, however, contradicts the fact that d(n2+4n)=d(n)+d(n+1)=2d(n)d\left(n^{2}+4 n\right)=d(n)+d(n+1)=2 d(n) has remainder 2 if d(n)d(n) has remainder 1, and vice versa.

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 translated into English from it; metadata (topic, difficulty) added by this project.