Prove that if $a$ is odd, then $a^2\equiv 1\pmod 8$

Question

Prove that if $a$ is odd, then $a^2\equiv 1\pmod 8$
I got this question in my discrete mathematics class, can anyone help me?
Thanks.

Answer 1

The clever way to do it is:

$a$ odd $\implies a -1$ and $a+1$ are two consecutive even numbers. As they are consecutive one of them is divisible by $4$ and the other is divisible by $2$. We have no way of knowing which is which but it doesn't matter. One is divisible by $2$ and the other is divisible by $4$ and multiplied together $(a-1)(a+1)$ is divisible by $8$.

So $(a-1)(a+1) \equiv 0 \mod 8$

So $a^2 -1 \equiv 0 \mod 8$

So $a^2 \equiv 1 \mod 8$.

=====

The brute force way is easier.

$a$ is odd means $a \equiv 1, 3, 5, \text{ or } 7 \mod 8$ so

$a^2 \equiv 1,9, 25, \text{ or } 49 \mod 8 \equiv 1 \mod 8$.

===

An intermediary method might by to realize $a = 2k + 1$ so $a^2 = 4k^2 + 4k + 1 = 4(k^2 + k) + 1$.

If $k$ is odd then $k^2$ is odd and $k^2 + k$ is even.

If $k$ is even then $k^2$ is even and $k^2 + k$ is even.

So $k^2 + k$ is divisible by $2$.

So $4(k^2 + k)$ is divisible by $8$.

So $4(k^2 + k) \equiv 0 \mod 8$

so $a^2 = 4(k^2 + k) + 1 \equiv 1 \mod 8$.

Answer 2

If $a$ is odd then $$a\equiv 1,3,5,7\pmod 8\Rightarrow a^2\equiv 1,9,25,49\pmod 8\Rightarrow a\equiv 1,1,1,1 \pmod 8.$$

Answer 3

If $a=2k+1$, then $$a^2=4k^2+4k+1=4k(k+1)+\mathbf{\color{blue}1}$$ Either $k$ or $k+1$ is even, and so $4k(k+1)$ is divisible by $8$. So after dividing $a^2$ by $8$ the remainder will be that $\mathbf{\color{blue}1}$.

Answer 4

When $a$ is odd, one has

$$a\equiv 1,3,5\text{ or } 7\pmod{8}$$

Now one has $\pmod{8}$

$$\begin{align} 1^2=&1\equiv 1\\3^2=&9\equiv 1\\5^2=&25\equiv 1\\7^2=&49\equiv 1\end{align}$$

Q.E.D

Answer 5

Since a is odd, suppose it is of the form 2k+1 for some integer k.

Then, $${a^2 = (4k^2 + 4k + 1) = 4k(k+1) +1}$$

Since k(k+1) is the product of two consecutive integers so one of them will be odd and other one will be even. Or you can say that k(k+1) can be written as 2m for some integer m.

Thus you get, $${a^2 = 4k(k+1) +1 = 8m+1}$$ That's what you wanted.