Logic Proof: Help Starting out I am having some trouble starting off this proof. I am not sure if I need to prove by the contrapositive or if it is a direct proof.
Prove: If $x, y,$ and $z$ are natural numbers such that $x^2+y^2=z^2$ and $gcd(x,y,z)=1$*, then exactly one of the natural numbers $x$ and $y$ is odd.
*$gcd$ is the greatest common divisor
I got that the contrapositive was: If it is not the case that exactly one of $x,y$ are odd, then $x^2+y^2\neq z^2$ or $gcd(x,y,z)=1$. Still not sure if I need to use the contrapositive in order to prove this
Thanks for any help!!
 A: Yes, using the contrapositive is probably the easiest way to do this. So start with the assumption that it is not true that exactly one of $x$ or $y$ are odd. Then either:


*

*Both $x$ and $y$ are even, or

*Both $x$ and $y$ are odd.


So you have to consider each of these cases separately.
Case 1. (This is the slightly easier case).
Assume $x,y$ are both even.
We want to show that one of the statements
$$x^2+y^2=z^2 \quad (1)$$
or
$$\gcd(x,y,z)=1 \quad (2)$$
is false.
The usual way to do this is to assume that one of them is true, and show that the other one has to be false.
Let us suppose that $x^2 + y^2$ indeed equals $z^2$. But $x$ and $y$ are even, so what does that tell you about $z^2 = x^2 + y^2$? Then, what does that tell you about $z$ itself? Hence what can you say about $\gcd(x,y,z)$?
(At this point it might be helpful to step back and have a review of the logical flow of our entire argument so far.)
Case 2. Assume $x,y$ are both odd. The logic in this part of the proof turns out to be slightly different from Case 1, as you will see. (Hint: you can directly show that one of the statements (1) or (2) is false, without having to assume the other.) Try beginning in the same way as you did for Case 1. Now what does this tell you about $z^2$? But what about $x^2+y^2$? Are the two expressions compatible? (Full solution hidden below:)

 Since $x$ and $y$ are both odd, so are $x^2$ and $y^2$, thus $z^2 = x^2 + y^2$ is even. (Odd + odd = even always, convince yourself of this.)
 It is easy to see that any even square number $z^2$ has to be divisible by $4$.
 On the other hand, since
 \begin{align} x &= 2m+1 \\ y &= 2n+1 \end{align}
 for some integers $m, n$ we know that $x^2+y^2 = 4k + 2$ for some integer $k$, but this is not divisible by $4$.
 Thus we cannot have $x^2+y^2 = z^2$, i.e. the square of two odd numbers is never a square.

Incidentally, this problem is the first step in finding all the primitive Pythagorean triples.
