[proofplan] We reduce the integer $a$ to its residue class modulo $4$. There are four possible residues, and squaring representatives $0,1,2,3$ gives only the residues $0$ and $1$ modulo $4$. Since congruence is preserved under multiplication, this determines the residue of $a^2$ modulo $4$. [/proofplan] [step:Choose the residue class of $a$ modulo $4$] Let $a \in \mathbb{Z}$. Choose integers $q \in \mathbb{Z}$ and $r \in \{0,1,2,3\}$ such that \begin{align*} a = 4q + r. \end{align*} Equivalently, \begin{align*} a \equiv r \pmod{4}. \end{align*} [guided] Let $a \in \mathbb{Z}$. We want to determine the possible residues of $a^2$ modulo $4$, so we first write $a$ in one of the four residue classes modulo $4$. Thus choose integers $q \in \mathbb{Z}$ and $r \in \{0,1,2,3\}$ such that \begin{align*} a = 4q + r. \end{align*} This means precisely that $4$ divides $a-r$, or equivalently \begin{align*} a \equiv r \pmod{4}. \end{align*} The four possible values of $r$ are therefore the only cases that can occur. [/guided] [/step] [step:Square each possible residue representative] Since $a \equiv r \pmod{4}$, there exists $m \in \mathbb{Z}$ such that $a-r=4m$. Then \begin{align*} a^2-r^2 &= (a-r)(a+r) \\ &= 4m(a+r), \end{align*} so $4$ divides $a^2-r^2$. Hence \begin{align*} a^2 \equiv r^2 \pmod{4}. \end{align*} Now compute the four possible values: \begin{align*} 0^2 &\equiv 0 \pmod{4}, \\ 1^2 &\equiv 1 \pmod{4}, \\ 2^2 = 4 &\equiv 0 \pmod{4}, \\ 3^2 = 9 &\equiv 1 \pmod{4}. \end{align*} Therefore $a^2 \equiv 0 \pmod{4}$ or $a^2 \equiv 1 \pmod{4}$. These two alternatives are mutually exclusive: if both congruences held, transitivity of congruence would give $0 \equiv 1 \pmod{4}$, so $4$ would divide $1$, which is impossible because no integer $k \in \mathbb{Z}$ satisfies $1 = 4k$. Hence exactly one of the two congruences holds. [guided] We now justify why replacing $a$ by its residue representative $r$ preserves the square modulo $4$. Since $a \equiv r \pmod{4}$, there is an integer $m \in \mathbb{Z}$ such that \begin{align*} a-r = 4m. \end{align*} Factoring the difference of squares gives \begin{align*} a^2-r^2 &= (a-r)(a+r) \\ &= 4m(a+r). \end{align*} Because $m(a+r) \in \mathbb{Z}$, the integer $4$ divides $a^2-r^2$. Therefore \begin{align*} a^2 \equiv r^2 \pmod{4}. \end{align*} It remains only to compute the square of each possible residue representative: \begin{align*} 0^2 &\equiv 0 \pmod{4}, \\ 1^2 &\equiv 1 \pmod{4}, \\ 2^2 = 4 &\equiv 0 \pmod{4}, \\ 3^2 = 9 &\equiv 1 \pmod{4}. \end{align*} Thus no matter which residue class $a$ belongs to modulo $4$, the square $a^2$ is congruent to either $0$ or $1$ modulo $4$. We also need to check that the two alternatives cannot happen simultaneously. Suppose, for contradiction, that both \begin{align*} a^2 \equiv 0 \pmod{4} \end{align*} and \begin{align*} a^2 \equiv 1 \pmod{4} \end{align*} hold. By transitivity and symmetry of congruence modulo $4$, this would imply \begin{align*} 0 \equiv 1 \pmod{4}. \end{align*} By the definition of congruence modulo $4$, this means that $4$ divides $1-0=1$. Thus there would be an integer $k \in \mathbb{Z}$ such that \begin{align*} 1 = 4k. \end{align*} No such integer exists, since $4k$ is divisible by $4$ for every $k \in \mathbb{Z}$ while $1$ is not divisible by $4$. Therefore the two congruences are mutually exclusive, and exactly one of them holds. [/guided] [/step]