# Divisiblity Proofs

• Apr 23rd 2009, 03:26 AM
shinn
Divisiblity Proofs
Can anyone give me some hints on the following problem:

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

Shinn
• Apr 23rd 2009, 04:22 AM
Soroban
Hello, Shinn!

Quote:

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

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

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

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

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

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

• Apr 23rd 2009, 04:30 AM
shinn
Is it correct if i prove "If $7 | x^2 + y^2$ then $7|x$ and $7 | y$" by the following:

Given $7 | x^2 + y^2$
Then, $7 | x^2$ and $7 |y^2$
(how would I write out a reason for this line?)
Thus, $7 | x$ and $7 |y$
• Apr 23rd 2009, 11:01 AM
clic-clac
Hi
I don't see any very easy proof.

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

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

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

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

Another way to show that would be to say that $\mathbb{Z}[i]$ is a factorial ring, that $7$ is an odd prime and $7\equiv 3(\text{mod}4)$ so it is irreducible in $\mathbb{Z}[i],$ and as a consequence $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.$