Divisiblity Proofs

**shinn** · April 23rd 2009, 02:26 AM

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$

Thanks in advance

Shinn

**Soroban** · April 23rd 2009, 03:22 AM

Hello, Shinn!

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)$

**shinn** · April 23rd 2009, 03:30 AM

**clic-clac** · April 23rd 2009, 10:01 AM

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.$

Thread: Divisiblity Proofs

LinkBack

Thread Tools

Display

Divisiblity Proofs

Similar Math Help Forum Discussions

Divisiblity test for 3

Help with log Proofs

More Proofs

Questions Involving Divisiblity

Sequence Convergence Proofs vs. Continuity Function Proofs

Search Tags