[proofplan] We classify the parities of $x$ and $y$ by reducing the equation modulo $4$. First, primitivity rules out the case that both $x$ and $y$ are even, because then the equation forces $z$ to be even as well. Next, the case that both $x$ and $y$ are odd is excluded because odd squares are congruent to $1$ modulo $4$, while no square is congruent to $2$ modulo $4$. The remaining possibility is that exactly one of $x$ and $y$ is even, and the original equation then forces $z$ to be odd. [/proofplan] [step:Record the possible residues of an integer square modulo $4$] Let $a \in \mathbb{Z}$. If $a$ is even, then there exists $k \in \mathbb{Z}$ such that $a = 2k$, and therefore \begin{align*} a^2 = 4k^2 \equiv 0 \pmod 4. \end{align*} If $a$ is odd, then there exists $k \in \mathbb{Z}$ such that $a = 2k+1$, and therefore \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$, and an integer square is congruent to $1$ modulo $4$ exactly when the integer is odd. [/step] [step:Exclude the case that both $x$ and $y$ are even] Assume, for contradiction, that both $x$ and $y$ are even. Then $x^2$ and $y^2$ are divisible by $4$, so \begin{align*} z^2 = x^2 + y^2 \equiv 0 \pmod 4. \end{align*} By the square-residue calculation above, this implies that $z$ is even. Hence $2$ divides each of $x$, $y$, and $z$, so \begin{align*} \gcd(|x|, |y|, |z|) \geq 2, \end{align*} contradicting the primitivity hypothesis $\gcd(|x|, |y|, |z|)=1$. Therefore $x$ and $y$ are not both even. [/step] [step:Exclude the case that both $x$ and $y$ are odd] Assume, for contradiction, that both $x$ and $y$ are odd. By the square-residue calculation, \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 every integer square is congruent to either $0$ or $1$ modulo $4$. Therefore $x$ and $y$ are not both odd. [/step] [step:Conclude that exactly one of $x$ and $y$ is even and that $z$ is odd] Every integer is either even or odd. Since $x$ and $y$ are neither both even nor both odd, exactly one of $x$ and $y$ is even and the other is odd. Suppose 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 equation gives \begin{align*} z^2 = x^2 + y^2 \equiv 1 \pmod 4. \end{align*} By the square-residue calculation, $z$ is odd. The case where $x$ is odd and $y$ is even is identical after interchanging the roles of $x$ and $y$: again $x^2+y^2 \equiv 1 \pmod 4$, hence $z^2 \equiv 1 \pmod 4$, and therefore $z$ is odd. Thus exactly one of $x$ and $y$ is even, the other is odd, and $z$ is odd. [/step]