# Thread: Prove: if (a,b,c) is a Pythagorean triple, then a and b cannot both be odd

1. ## Prove: if (a,b,c) is a Pythagorean triple, then a and b cannot both be odd

Intro exercise:
Show that any integer square leaves remainder 0 or 1 on division by 4.
$\displaystyle a_{even}=2k$: $\displaystyle a^2=(2k)^2=4(k^2)=0\mod{4}$
$\displaystyle a_{odd}=2k-1$: $\displaystyle a^2=(2k-1)^2=4(k^2-k)+1=1\mod{4} \square$
Deduce from above exercise that if $\displaystyle (a,b,c)$ is a Pythagorean triple, then $\displaystyle a$ and $\displaystyle b$ cannot both be odd.
$\displaystyle c^2=a^2+b^2 \xrightarrow{?} c^2\mod{4}=(a^2+b^2)\mod{4}=\left\{ \begin{array}{ll} 0 & \mbox{;$a^2=0\mod{4} \text{ AND } b^2=0\mod{4}$};\\ 1 & \mbox{;$a^2=1\mod{4} \text{ XOR } b^2=1\mod{4}$}.\end{array} \right. \square$

Are my two tries above worth the halmos $\displaystyle \square$ sign?

2. Originally Posted by courteous
Intro exercise:$\displaystyle a_{even}=2k$: $\displaystyle a^2=(2k)^2=4(k^2)=0\mod{4}$
$\displaystyle a_{odd}=2k-1$: $\displaystyle a^2=(2k-1)^2=4(k^2-k)+1=1\mod{4} \square$
$\displaystyle c^2=a^2+b^2 \xrightarrow{?} c^2\mod{4}=(a^2+b^2)\mod{4}=\left\{ \begin{array}{ll} 0 & \mbox{;$a^2=0\mod{4} \text{ AND } b^2=0\mod{4}$};\\ 1 & \mbox{;$a^2=1\mod{4} \text{ XOR } b^2=1\mod{4}$}.\end{array} \right. \square$

Are my two tries above worth the halmos $\displaystyle \square$ sign?
(Edited)

Hmm for the intro normally I would do the easy thing and just check all equivalence classes mod 4 exhaustively.

$\displaystyle 0^2 \equiv 0\bmod{4}$
$\displaystyle 1^2 \equiv 1\bmod{4}$
$\displaystyle 2^2 \equiv 0\bmod{4}$
$\displaystyle 3^2 \equiv 1\bmod{4}$

But it seems that to check squares mod n^2 it is sufficient to check the equivalence classes mod n, and what you did is good.

For the second part, I think it's best to rewrite since the theorem we want to prove involves a,b odd, for which we know $\displaystyle a^2 + b^2 \equiv 1+1 \equiv 2 \bmod{4}$. (You had this but it's not really explicit the way you wrote it, since you omitted the case a,b odd.)

by the way to get $\displaystyle \,\equiv$ in LaTeX you can use the command \equiv.