Maths Olympiad Prep

Library / /26 of 65

Number theory Difficulty 5.7 AIME, harder Prove it Romania

Prove that a positive integer AA is a perfect square if and only if, for all positive integers nn, at least one of the numbers
(A+1)2A,(A+2)2A,(A+3)2A,,(A+n)2A (A+1)^2 - A, (A+2)^2 - A, (A+3)^2 - A, \dots, (A+n)^2 - A
is a multiple of nn.

Solution

If AA is a perfect square, i.e. there exists BNB \in \mathbb{N} such that A=B2A = B^2, then (A+k)2A=(B2+k)2B2=(B2+B+k)(B2B+k)(A+k)^2 - A = (B^2+k)^2 - B^2 = (B^2+B+k)(B^2-B+k) for all k=1,nk = 1, n, and exactly one of the (consecutive) numbers B2+B+1,B2+B+2,,B2+B+nB^2+B+1, B^2+B+2, \dots, B^2+B+n is a multiple of nn.

Conversely, if AA is not a perfect square, then it has a prime factor that occurs in the prime factorization of AA at an odd exponent. Let pp be such a prime and jNj \in \mathbb{N} such that p2j1Ap^{2j-1} \mid A, but p2jAp^{2j} \nmid A. We choose n=p2jNn = p^{2j} \in \mathbb{N} and show that none of the numbers (A+1)2A,(A+2)2A,(A+3)2A,,(A+n)2A(A+1)^2-A, (A+2)^2-A, (A+3)^2-A, \dots, (A+n)^2-A is a multiple of nn. Indeed, if n(A+m)2An \mid (A+m)^2-A, for some m{1,2,,n}m \in \{1, 2, \dots, n\}, i.e. p2jA2+2Am+m2Ap^{2j} \mid A^2 + 2Am + m^2 - A, from p2j1Ap^{2j-1} \mid A it follows that p2j1m2p^{2j-1} \mid m^2, hence pjmp^j \mid m. But then p2j(A+m)2p^{2j} \mid (A+m)^2 and p2j(A+m)2Ap^{2j} \mid (A+m)^2 - A, hence p2jAp^{2j} \mid A, which is a contradiction.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.