1. ## Divisiblity Proofs

Can anyone give me some hints on the following problem:

For integers x and y, show that $\displaystyle 7 | x^2 + y^2$ if and only if $\displaystyle 7 | x$ and $\displaystyle 7 | y$

Shinn

2. Hello, Shinn!

For integers $\displaystyle x$ and $\displaystyle y$, show that: .$\displaystyle 7 |( x^2 + y^2)\:\text{ if and only if }\:7 | x\,\text{ and }\,7 | y$
I'll do the "only if" part . . .

$\displaystyle \text{Prove: }\:\text{If }\,7|x\,\text{ and }\,7|y\,\text{, then }\,7|(x^2+y^2)$

Since $\displaystyle 7|x,\;\;x \:=\:7a\,\text{ for some integer }a$
Since $\displaystyle 7|y,\;\;y \:=\:7b\,\text{ for some integer }b$

Then: .$\displaystyle \begin{array}{ccccc}x^2 &=& (7a)^2 &=& 49a^2 \\ y^2 &= & (7b)^2 &=& 49b^2 \end{array}$

Hence: .$\displaystyle x^2+y^2\:=\:49a^2 + 49b^2 \:=\:7(7a^2+7b^2) \quad\hdots\;\text{ a multiple of 7}$

Therefore: .$\displaystyle 7|(x^2+y^2)$

3. Hi, thanks for the reply.
Is it correct if i prove "If $\displaystyle 7 | x^2 + y^2$ then $\displaystyle 7|x$ and $\displaystyle 7 | y$" by the following:

Given $\displaystyle 7 | x^2 + y^2$
Then, $\displaystyle 7 | x^2$ and $\displaystyle 7 |y^2$
(how would I write out a reason for this line?)
Thus, $\displaystyle 7 | x$ and $\displaystyle 7 |y$

4. Hi
I don't see any very easy proof.

Maybe you can do that using a contraposition proof:
assume $\displaystyle 7$ doesn't divide $\displaystyle x$ nor $\displaystyle y,$ i.e. there are integers $\displaystyle k,l\in\{1,2,3,4,5,6\}$ such that $\displaystyle x\equiv k(\text{mod}7)$ and $\displaystyle y\equiv l(\text{mod}7)$

Then $\displaystyle x^2+y^2\equiv n+m(\text{mod}7)$ where $\displaystyle n,m\in\{1,2,4\} \ \ \ (*)$

therefore $\displaystyle x^2+y^2\neq 0(\text{mod}7)$ i.e. $\displaystyle 7$ does not divide $\displaystyle x^2+y^2.$

To prove $\displaystyle (*),$ compute all squares in $\displaystyle \mathbb{Z}_7.$

Another way to show that would be to say that $\displaystyle \mathbb{Z}[i]$ is a factorial ring, that $\displaystyle 7$ is an odd prime and $\displaystyle 7\equiv 3(\text{mod}4)$ so it is irreducible in $\displaystyle \mathbb{Z}[i],$ and as a consequence $\displaystyle 7|x^2+y^2\Rightarrow 7|(x+iy)(x-iy)\Rightarrow 7|x+iy\ \text{or}\ 7|x-iy \Rightarrow 7|x\ \text{and}\ 7|y.$