[proofplan] We prove the parity statement by eliminating the two impossible parity configurations for $x$ and $y$. If both legs are even, the Pythagorean equation forces $z$ to be even, contradicting primitivity. If both legs are odd, reducing the equation modulo $4$ gives $z^2 \equiv 2 \pmod{4}$, impossible because every square is congruent to $0$ or $1$ modulo $4$. Therefore exactly one of $x$ and $y$ is even, and substituting this parity back into the equation forces $z^2$, hence $z$, to be odd. [/proofplan] [step:Record the possible residues of a square modulo $4$] For any integer $n \in \mathbb{Z}$, exactly one of $n$ and $n-1$ is even. Hence either $n=2k$ for some $k \in \mathbb{Z}$, or $n=2k+1$ for some $k \in \mathbb{Z}$. In the first case, \begin{align*} n^2 = (2k)^2 = 4k^2 \equiv 0 \pmod{4}. \end{align*} In the second case, \begin{align*} n^2 = (2k+1)^2 = 4k^2 + 4k + 1 \equiv 1 \pmod{4}. \end{align*} Thus every integer square is congruent to either $0$ or $1$ modulo $4$. [/step] [step:Exclude the case in which both $x$ and $y$ are even] Suppose, for contradiction, that $x$ and $y$ are both even. Then there exist integers $a,b \in \mathbb{Z}$ such that \begin{align*} x = 2a, \qquad y = 2b. \end{align*} Using $x^2+y^2=z^2$, we get \begin{align*} z^2 = x^2 + y^2 = (2a)^2 + (2b)^2 = 4(a^2+b^2). \end{align*} Thus $z^2$ is divisible by $4$, so $z^2 \equiv 0 \pmod{4}$. Since an odd square is congruent to $1$ modulo $4$, the integer $z$ cannot be odd. Therefore $z$ is even. Hence $2$ divides each of $x$, $y$, and $z$, so $2$ is a common divisor of $x,y,z$. This contradicts $\gcd(x,y,z)=1$. Therefore $x$ and $y$ cannot both be even. [/step] [step:Exclude the case in which both $x$ and $y$ are odd] Suppose, for contradiction, that $x$ and $y$ are both odd. By the square-residue computation above, \begin{align*} x^2 \equiv 1 \pmod{4}, \qquad y^2 \equiv 1 \pmod{4}. \end{align*} Adding these congruences gives \begin{align*} x^2+y^2 \equiv 2 \pmod{4}. \end{align*} Since $x^2+y^2=z^2$, this implies \begin{align*} z^2 \equiv 2 \pmod{4}. \end{align*} But every integer square is congruent to either $0$ or $1$ modulo $4$, never to $2$ modulo $4$. This contradiction shows that $x$ and $y$ cannot both be odd. [/step] [step:Conclude that exactly one leg is even and the hypotenuse is odd] Every integer is either even or odd. The preceding two steps show that $x$ and $y$ are neither both even nor both odd. Therefore exactly one of $x$ and $y$ is even. Assume first that $x$ is even and $y$ is odd. Then \begin{align*} x^2 \equiv 0 \pmod{4}, \qquad y^2 \equiv 1 \pmod{4}, \end{align*} so the Pythagorean equation gives \begin{align*} z^2 = x^2+y^2 \equiv 1 \pmod{4}. \end{align*} Thus $z^2$ is odd, and therefore $z$ is odd. The case where $x$ is odd and $y$ is even is identical with $x$ and $y$ interchanged: again \begin{align*} z^2 = x^2+y^2 \equiv 1 \pmod{4}, \end{align*} so $z$ is odd. Hence exactly one of $x$ and $y$ is even, and $z$ is odd. [/step]