The questions asks, "Show that the square of any integer is congruent to either $0$, $1$, or $4 \pmod 8$".
The answer starts off by stating, "Every number is congruent to $0, 1, 2, 3, 4, 5, 6 $ or $7\pmod 8$", however I don't understand why this is the case.
(The full answer: "Every number is congruent to $0, 1, 2, 3, 4, 5, 6$ or $7$ (mod $8$). The squares are thus congruent to either $0, 1, 4, 9 \equiv 1, 16 \equiv 0, 36 \equiv 4$, or $49 \equiv 1$. We don't need to try higher numbers because all higher numbers can be modded out before squaring.")
$\endgroup$ 51 Answer
$\begingroup$If $x$ is congruent to $y$ modulo $a$, that means that $x$ and $y$ have the same remainder when divided by $a$, i.e., $x-y$ is a multiple of $a$.
As a consequence of the long division algorithm over the integers, for any $a \neq 0$, and any integer $x$, we can write $x = Qa+R$, where $Q,R$ are integers and $R \in \{0,1,\ldots,a-1\}$; $Q$ corresponds to the "quotient" and $R$ to the remainder. Since $x-R$ is a multiple of $a$, then, $x \equiv R \pmod{a}$. Thus, every integer is congruent to one of the values $\{0,1,\ldots,a-1\}$, modulo $a$.
For instance, in the case $a=2$, the statement above implies that every integer is either a multiple of two (i.e., even), or a multiple of two plus one (i.e., odd). In the case $a=8$, the result is slightly less intuitive, but equally true: Every element, when divided by 8, has remainder either 0,1,2,3,4,5,6, or 7.
$\endgroup$
