Maths Olympiad Prep

Library / /199 of 520

Number theory Difficulty 6.7 National olympiad Prove it

Let S={nn1,n,n+1S=\{n|n-1,n,n+1 can be expressed as the sum of the square of two positive integers.}\}. Prove that if nn in SS, n2n^{2} is also in SS.

Solution

1. Let S={nn1,n,n+1 can be expressed as the sum of the squares of two positive integers} S = \{ n \mid n-1, n, n+1 \text{ can be expressed as the sum of the squares of two positive integers} \} . We need to prove that if nS n \in S , then n2S n^2 \in S .

2. Suppose nS n \in S . This means there exist positive integers a,b,k,,p,q a, b, k, \ell, p, q such that:
{a2+b2=n1k2+2=np2+q2=n+1 \begin{cases} a^2 + b^2 = n - 1 \\ k^2 + \ell^2 = n \\ p^2 + q^2 = n + 1 \end{cases}

3. We know that for any integer x x , x20 or 1(mod4) x^2 \equiv 0 \text{ or } 1 \pmod{4} . Therefore:
n1,n,n+10,1,2(mod4) respectively n-1, n, n+1 \equiv 0, 1, 2 \pmod{4} \text{ respectively}

4. We need to show that n21,n2,n2+1 n^2 - 1, n^2, n^2 + 1 can also be expressed as the sum of the squares of two positive integers.

5. Using the identity for the product of sums of squares:
(a2+b2)(c2+d2)=(acbd)2+(ad+bc)2 (a^2 + b^2)(c^2 + d^2) = (ac - bd)^2 + (ad + bc)^2

6. Applying this identity, we get:
n21=(k2+21)=(a2+b2)(p2+q2)=(apbq)2+(aq+bp)2 n^2 - 1 = (k^2 + \ell^2 - 1) = (a^2 + b^2)(p^2 + q^2) = (ap - bq)^2 + (aq + bp)^2
This shows that n21 n^2 - 1 can be expressed as the sum of the squares of two positive integers.

7. For n2 n^2 , we use the identity:
n2=(k2+2)2=(k2+2)(k2+2)=(k22)2+(2k)2 n^2 = (k^2 + \ell^2)^2 = (k^2 + \ell^2)(k^2 + \ell^2) = (k^2 - \ell^2)^2 + (2k\ell)^2
This shows that n2 n^2 can be expressed as the sum of the squares of two positive integers.

8. Finally, for n2+1 n^2 + 1 :
n2+1=(k2+2)2+1 n^2 + 1 = (k^2 + \ell^2)^2 + 1
Since k k \neq \ell , we can use the identity again to show that n2+1 n^2 + 1 can be expressed as the sum of the squares of two positive integers.

Therefore, if nS n \in S , then n2S n^2 \in S .

\blacksquare

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.