The square of an integer is congruent to 0 or 1 mod 4

This is a question from the free Harvard online abstract algebra lectures. I'm posting my solutions here to get some feedback on them. For a fuller explanation, see this post.

This problem is from assignment 6. The notes from this lecture can be found here.

a) Prove that the square $a^2$ of an integer $a$ is congruent to 0 or 1 modulo 4.
b) What are the possible values of $a^2$ modulo 8?

a) Let $a$ be an integer. Then $a=4q+r, 0\leq r<4$ with $\bar{a}=\bar{r}$. Then we have $a^2=a\cdot a=(4q+r)^2=16q^2+8qr+r^2=4(4q^2+2qr)+r^2, 0\leq r^2<4$ with $\bar{a^2}=\bar{r^2}$. So then the possible values for $r$ with $r^2<4$ are 0,1. Then $\bar{a^2}=\bar{0}$ or $\bar{1}$.

b) Let $a$ be an integer. Then $a=8q+r, 0\leq r<8$ with $\bar{a}=\bar{r}$. Then we have $a^2=a\cdot a=(8q+r)^2=64q^2+16qr+r^2=8(8q^2+2qr)+r^2, 0\leq r^2<8$ with $\bar{a^2}=\bar{r^2}$. So then the possible values for $r$ with $r^2<8$ are 0,1,and 2. Then $\bar{a^2}=\bar{0}$, $\bar{1}$ or $\bar{4}$.

Again, I welcome any critique of my reasoning and/or my style as well as alternative solutions to the problem.

Thanks.

Solution 1:

Suppose the integer $z$ is even. Write it as $z = 2n$, where $n\in\mathbb{Z}$. Then $z^2 = 4n^2$; $z$ is divisible by 4. Suppose the integer $z$ is odd. Write it as $z = 2n + 1$ where $n\in\mathbb{Z}$; then $z^2 = 4n^2 + 4n + 1 = 4n(n+1) + 1.$

We have just shown that for any integer $z$, the square of $z$, when divided by 4 gives remainder 1 or 0.

Solution 2:

For the first one the idea of what you have done is right (although did you mean to say that since $0 \leq r < 4$, $0 \leq r^2 < 16$?). An alternative viewpoint is to look at it like this. Define an equivalence relation $\sim$ on the integers by $x\sim y$ iff $x - y $ is a multiple of $4$. Then you can check that this is an equivalence relation, so that you know every integer in the universe is of the form $4k$, $4k+1$, $4k+2$, or $4k+3$. This is basically the division algorithm.

If you square each one of these, the first one is $16k^2 \equiv 0 $ mod $4$, the second is congruent to 1 mod 4, the third is congruent to zero mod 4 because $2^2 = 4$ and the last is congruent to 1 mod 4 because $(4k+3)^2 = 4(\text{stuff}) + 1$.

The second problem is a casebash too (just this time you're working mod 8 as you have done).

Alternatively, there is another way to look at this in terms of group theory. I'm mentioning this because you are studying groups and one way or another you will come to this. Consider the integers $\mathbb{Z}$ as a group. For question (a), let $\pi$ be the canonical projection from $\mathbb{Z}$ to $\mathbb{Z}/(4)$, where $(4)$ is the cyclic normal subgroup of $\mathbb{Z}$ consisting of all the multiples of $4$. $\pi$ is a map that sends each integer to its equivalence class, where the equivalence relation here is

$$x \sim y \hspace{3mm} \text{iff} \hspace{3mm} x - y \in (4).$$

Let us write $[a]$ for the equivalence class of an integer in the quotient $\mathbb{Z}/(4)$. Now multiplication in the quotient is well-defined because $(4)$ is a normal subgroup, so that $[a \times a] = [a] \times [a]$. There is no ambiguity in using $\times$ for both as it is just ordinary multiplication of integers.

What this means is when looking at the possible remainders of the square of an integer mod 4, you can just concentrate on calculating

$$ \begin{eqnarray} 0^2 &\equiv& 0 \hspace{2mm} \text{mod} \hspace{2mm} 4\\ 1^2 &\equiv& 1 \hspace{2mm} \text{mod} \hspace{2mm} 4 \\ 2^2 &\equiv& 0 \hspace{2mm} \text{mod} \hspace{2mm} 4\\ 3^2 &\equiv& 1 \hspace{2mm} \text{mod} \hspace{2mm} 4. \end{eqnarray}$$ This is because given any integer $[a]$, $[a] = [0],[1],[2]$ or $[3]$. Similarly for (b) your problem reduces to calculating the squares of $0,1,2 \ldots 7$ mod $8$.

Hope this helps!

Solution 3:

$$\begin{align} x^2 \mod 4 &\equiv (x \mod 4)(x \mod 4) \pmod 4 \\ &\equiv \begin{cases}0^2 \mod 4 \\ 1^2 \mod 4 \\ 2^2 \mod 4 \\ 3^2 \mod 4 \end{cases} \\ &\equiv \begin{cases}0 \mod 4 \\ 1 \mod 4 \\ 4 \mod 4 \\ 9 \mod 4 \end{cases} \\ &\equiv \begin{cases}0 \mod 4 \\ 1 \mod 4 \\ 0 \mod 4 \\ 1 \mod 4 \end{cases} \end{align} $$

Solution 4:

Hint $ $ Division $\rm\Rightarrow n = 4q\! +\! r,\ r\in \{0\ 1\ 2\ 3\}\Rightarrow n^2 = (4q\!+\!r)^2 =$ $\rm\: 4(4q^2\!+\!2qr)\!+\!r^2 = $ $\rm\:4Q\! +\! \color{#c00}{r^2}.\,$ For the remainder of $\rm\,r^2\,$ note: $\,\rm r\in \{0\ 1\ 2\ 3\}$ $\rm\Rightarrow\, \color{#c00}{r^2 = \,4 \bar q + \bar r},\ \bar r\in \{0\ 1\},\,$ so $\rm \, n^2 = 4Q\!+\!\color{#c00}{4\bar q + \bar r}$

It's simpler in modular language $\rm\ mod\ 4\!:\ n\equiv r\ \Rightarrow\ n^2 \equiv r^2\equiv \{0\ 1\ 2\ 3\}^2\equiv \{0\ 1\ \color{#c00}4\ \color{#0a0}9\}\equiv \{\color{#c00}0\ \color{#0a0}1\}\, $ by applying Congruence Product Rule, or working in the quotient / residue ring $\rm\ \mathbb Z/4\, =\, \mathbb Z\ mod\ 4.$

Optimization: work is halved employing a balanced residue system, e.g. $\rm\: \pm \{0\ 1\ 2\ 3\ 4\}\ mod\ 8.\ $ Using that we quickly compute $\rm\ mod\ 8\!:\ odd^2\equiv \{ 1 \ 3\}^2 \equiv 1,\ \: even^2 \equiv \{0\ 2\ 4\}^2 \equiv \{0\ 4\}.$

Or we can halve the cases via LTE: $\ \rm n\equiv r\pmod{\!2m}\Rightarrow n^2\equiv r^2\pmod{\!4m}\,$

Solution 5:

The glitch I am going to point out is not very serious, though keeping tracking of such things helps.

For instance, in (a), how is $0\leq r^2<4$. Consider a number of the form $4q+2$, you'll have an issue. But, however, what follows this error, $\bar a^2=\bar r^2$ is correct. But Why? Because, the the remainder when $ a^2$ is divided by $4$ is the same as that when $ r^2$ is divided by $4$ is what the equation reads and what you have proved.

So, to really complete the solution, you need to take a case-by-case approach. For various possible values of $r$, prove that $\bar r^2$ is as claimed.

Remark: It is an equivalence that $a=4q+r, 0\leq r<4 \iff \bar a=\bar r$. So, your statement that, "[...]Then $a=4q+r,0 \leq r<4~ \text {with}~ \bar a=\bar r$[...]" is a little clumsy.

The same remarks go for (b).

Hope this helps.