[proofplan] We argue by congruences modulo $4$. Squares of integers are congruent only to $0$ or $1$ modulo $4$, so two odd legs would force $z^2 \equiv 2 \pmod 4$, which is impossible. Two even legs would force $z$ even as well, contradicting primitivity. Therefore exactly one leg is even, and substituting this parity back into $x^2+y^2=z^2$ shows that $z^2 \equiv 1 \pmod 4$, hence $z$ is odd. [/proofplan] [step:Record the possible square residues modulo $4$] Let $a \in \mathbb{Z}$. If $a$ is even, then $a = 2k$ for some $k \in \mathbb{Z}$, so \begin{align*} a^2 = 4k^2 \equiv 0 \pmod 4. \end{align*} If $a$ is odd, then $a = 2k+1$ for some $k \in \mathbb{Z}$, so \begin{align*} a^2 = 4k^2 + 4k + 1 \equiv 1 \pmod 4. \end{align*} Thus every integer square is congruent to either $0$ or $1$ modulo $4$, with residue $0$ exactly for even integers and residue $1$ exactly for odd integers. [/step] [step:Exclude the case where both legs are odd] Suppose, for contradiction, that both $x$ and $y$ are odd. By the square-residue computation above, \begin{align*} x^2 \equiv 1 \pmod 4, \qquad y^2 \equiv 1 \pmod 4. \end{align*} Using $x^2+y^2=z^2$, we obtain \begin{align*} z^2 = x^2+y^2 \equiv 1+1 \equiv 2 \pmod 4. \end{align*} This contradicts the fact that an integer square is congruent only to $0$ or $1$ modulo $4$. Therefore $x$ and $y$ are not both odd. [/step] [step:Exclude the case where both legs are even] Suppose, for contradiction, that both $x$ and $y$ are even. Then $x^2$ and $y^2$ are divisible by $4$, so $z^2=x^2+y^2$ is divisible by $4$. Hence $z^2$ is even, and therefore $z$ is even. Thus $2$ divides each of $x$, $y$, and $z$, so \begin{align*} 2 \mid \gcd(x,y,z). \end{align*} This contradicts the primitivity hypothesis $\gcd(x,y,z)=1$. Therefore $x$ and $y$ are not both even. [/step] [step:Conclude that exactly one leg is even and the hypotenuse is odd] Every integer is either even or odd. Since $x$ and $y$ are neither both odd nor both even, exactly one of $x$ and $y$ is even, and the other is odd. 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 0+1 \equiv 1 \pmod 4. \end{align*} Hence $z$ is odd, because an even integer has square congruent to $0$ modulo $4$. The case where $x$ is odd and $y$ is even is identical after interchanging $x$ and $y$: again $x^2+y^2 \equiv 1 \pmod 4$, so $z^2 \equiv 1 \pmod 4$, and therefore $z$ is odd. This proves that $z$ is odd and exactly one of $x$ and $y$ is even. [/step]