Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Discrete mathematics, continuous mathematics, and probability / 2 / b

Suppose, for a proof by contradiction, that an integer $n$ is both an even number and an odd number. Then $n=2u$ and $n=2v+1$ for some integers $u,v$. Subtracting yields $u-v=1/2$. The left side is an integer, while $1/2$ is not. This contradiction proves that no integer is both even and odd.

The contrapositive is that an integer perfect square has residue $0$ or $1$ modulo $4$. Let $n=t^2$ for an integer $t$. If $t=2u$ is an even number, then $t^2=4u^2\equiv 0(\mathrm{mod}4)$. If $t=2u+1$ is an odd number, then $t^2=4u(u+1)+1\equiv 1(\mathrm{mod}4)$. These exhaust the possible parities of an integer. Thus a residue of $2$ or $3$ excludes being a perfect square, as required by the contrapositive.