# How to show that $7\mid a^2+b^2$ implies $7\mid a$ and $7\mid b$?

For my proof I distinguished the two possible cases which derive from $7 \mid a^2+b^2$:

Case one: $7\mid a^2$ and $7 \mid b^2$
Case two (which (I think) is not possible): $7$ does not divide $a^2$ and $7$ does not divide $b^2$, but their sum.

I've shown that case $1$ implies $7\mid a$ and $7\mid b$, so I just have show that case 2 isn't possible
- I'll be happy for any input.

MfG, Karl

• If $a$ is not divisible by $7$, then $a$ is congruent to $1$, or to $2$, and so on up to $6$ (modulo $7$). So $a^2$ is congruent to one of $1$, $2$, or $4$. Same with $b^2$. Now find all possible values of $a^2+b^2$ modulo $7$. Mar 23 '14 at 19:57
• Nov 22 '15 at 6:55
• See also: Prove $7|x^2+y^2$ iff $7|x$ and $7|y$. Aug 7 '17 at 19:17

For the sum just look at $a^2 \mod 7$: it can only be $0,1,2$ or $4$. So unless both $a$ and $b$ are divisible by $7$, $a^2 + b^2$ cannot be divisible by $7$.

The squares of the residues modulo $7$ are $1$,$2$,and $4$. Sums of these are $2,3,4,5,6,8$ which are congruent to $1,2,3,4,5,6$ but not $7$. Therefore $7$ does not divide the sum of two squares.

Hint $\,{\rm mod\ 7}\!:\ a,b\not\equiv\, 0\,\Rightarrow\ a^2\!+b^2\not\equiv 0,\,$ else $\,a^2\equiv -b^2\,\overset{\rm\large cube}\Rightarrow\,1\equiv a^6\equiv-b^6\equiv -1\,$ by Fermat.

Hint

$\mod 7$ we have $x^2=0,1$ or $4$ so $$a^2+b^2=0\Rightarrow (a=0)\land(b=0)\mod 7$$

a = 7k + m, and b = 7p + n ==> a^2 + b^2 = m^ + n^2 ( mod 7 ).

Case 1: m = 1, n = 1 => m^2 + n^2 = 2. ( mod 7 )

Case 2: m = 1, n = 2 => m^2 + n^2 = 5.

Case 3: m = 1, n = 3 => m^2 + n^2 = 3.

Case 4: m = 1, n = 4 => m^2 + n^2 = 3.

Case 5: m = 1, n = 6 => m^2 + n^2 = 2.

.... All cases yield non-zero mod 7. So it can happen only when both a and b are 0 mod 7.