Olympiad Maths Prep

Track / Stage 5 / 383 of 400 #983 of 2000

Problem 983

AIME late
Number theory Difficulty 6.0 Prove it

Example 14 (2006 Western China Mathematical Olympiad) Let S={nn1,n,n+1S=\{n \mid n-1, n, n+1 can all be expressed as the sum of two positive integers squared }\}. Prove: if nSn \in S, then n2Sn^{2} \in S.

---

The translation maintains the original text's line breaks and format as requested.

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

Notice that if x,yx, y are integers, then by parity analysis we know
x2+y20,1,2(mod4) x^{2}+y^{2} \equiv 0,1,2(\bmod 4) \text {. }

If nSn \in S, then from the above, n1(mod4)n \equiv 1(\bmod 4). Thus, we can set
n1=a2+b2,ab,n=c2+d2,c>d(c,d cannot be equal ),n+1=e2+f2,ef, \begin{array}{l} n-1=a^{2}+b^{2}, a \geqslant b, \\ n=c^{2}+d^{2}, c>d(c, d \text { cannot be equal }), \\ n+1=e^{2}+f^{2}, e \geqslant f, \end{array}

where a,b,c,d,e,fa, b, c, d, e, f are all positive integers.
Then n2+1=n2+12,n2=(c2+d2)2=(c2d2)2+(2cd)2n^{2}+1=n^{2}+1^{2}, n^{2}=\left(c^{2}+d^{2}\right)^{2}=\left(c^{2}-d^{2}\right)^{2}+(2 c d)^{2},
n21=(a2+b2)(e2+f2)=(aebf)2+(af+be)2 n^{2}-1=\left(a^{2}+b^{2}\right)\left(e^{2}+f^{2}\right)=(a e-b f)^{2}+(a f+b e)^{2} \text {. }

Assume b=ab=a, and f=ef=e, then n1=2a2,n+1=2e2n-1=2 a^{2}, n+1=2 e^{2}, subtracting the two equations gives e2a2=1e^{2}-a^{2}=1, then ea1e-a \geqslant 1, and 1=e2a2=(e+a)(ea)>11=e^{2}-a^{2}=(e+a)(e-a)>1, a contradiction!
Therefore, b=a,f=eb=a, f=e cannot both hold. So aebf>0a e-b f>0, thus n2Sn^{2} \in S.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.