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.
Best Answer
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.