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

• Sep 25th 2010, 10:21 AM
courteous
Prove: if (a,b,c) is a Pythagorean triple, then a and b cannot both be odd
Intro exercise:
Quote:

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$
Quote:

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? (Itwasntme)
• Sep 25th 2010, 10:38 AM
undefined
Quote:

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? (Itwasntme)

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