Find all solutions to $x^2$ ≡ 1(mod 8)

Question

Find all solutions to $x^2$ ≡ 1 in arithmetic modulo 8.

My understanding is that what this is saying is that find the x which multiplicative inverse is equal to itself within modulo 8.

I know that this is the case for certain examples like in modulo 18: the multiplicative inverse of 17 is also 17. But I am not quite sure why.

Any explanation and help with a technique to solve would be appreciated.

Answer 1

Well there's always trial an error and the will give you insight.

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

$2^2 \equiv 4; 3^3 \equiv 1 \mod 8; 4^2 \equiv 0 \mod 8; 5^2\equiv 1 \mod 8; 6^2\equiv 4\mod 8; 7^2 \equiv 1\mod 8; 0^2 \equiv 0 \mod 8$

So the answer is $1, 3,5,7$ which seems to be the odd numbers but why would this be?

Well, you can always you the quadratic formula.

$x^2 \equiv 1 \mod 8$

$x^2 - 1 \equiv 0 \mod 8$

$x^2 - 1 -8k = 0$ for some integer $k$

$x = \frac {\pm \sqrt{4(1+8k)}}2 = \pm \sqrt{1+8k}$

If $k = 0$ then $x = \pm1$ and if $k=1$ and if $k = 1$ then $x =\pm 3$. so that gives us $1,3,5,7$.

But that's still not satisfying because it is still trial and error and who knows if there is any $k> 1$ where $1 +8k$ is a perfect square.

But $x^2 \equiv 1 \mod 8$ means $x^2 -1 = (x-1)(x+1) \equiv 0 \mod 8$. so this is a matter of finding the factors of $0$ and adding and subtracting $1$ from them.

Obiviously lettting one of $x+1; x-1$ being equiv $0$ will yield a solution: $x\pm 1 \equiv 0\mod 8$ so $x\equiv \mp 1 \mod 8$ will be options so that accounts for $1, 7$.

The non-zero factors are: $m,8k;$ and $2j;4m$.

Or in other words: $(0,x),(1,0), (2,4),(4,4),(6,4)$.

If $x \pm 1 \equiv 0$ then $x = 1, 7$

If $x\pm 1\equiv 1 \mod 8$ while $x \mp 1 \equiv 0 \mod 8$ means $x\equiv 0,2$ while $x \equiv 1,7$ which is impossible.

If $x \pm 1 \equiv 2$ while $x \mp 1 \equiv 4$ means $x\equiv 1,3$ while $x \equiv 5,3$ so $x = 3$.

$x +1 \equiv 4 \equiv x-1$ is impossible.

And if $x\pm 1\equiv 6\implies x\equiv 5,7$ and $x\mp \equiv 4 \implies x \equiv 5,3$ so $x = 3$.

Hence $x = 1,3,5,7$ and we hopefully have a hint why the odd numbers were the answers (because the factors of $0\mod 8$ are $2,4$ and are equiv to $x\pm 1$) and how to solve in genernal. (Factor and find the divisors of $0$ and set equal to the factors).

Answer 2

Something a little less tedious than trial and error:

Write down all the square numbers modulo $8$ for the first half of the numbers and then see if any of them are $1$. Then since you are looking at squares, the following numbers after the "half-way" mark will be the same list but in reverse (so if $n^2\equiv1\mod8$ then $(-n)^2\equiv1\mod8$). This explains why $17$ is its own multiplicative inverse because

$$17\mod 18=-1\mod 18\Rightarrow17^2\mod18=1\mod18$$

Every number can be written as $0,\pm1,\pm2,\pm3,4\mod8$

Answer 3

$x^2\equiv 1\ (\mod 8)\\ x^2-1\equiv0\ (\mod 8)\\ (x-1)(x+1)\equiv0\ (\mod 8)\\ 8\mid(x-1)(x+1) $

By trial and error, we get $x\equiv a\ (\mod8)$, where $a\in\{1,7,3,5\}$.

Answer 4

Hint:  can $\,x\,$ be even? If not, then $x^2-1=(x-1)(x+1)$ is a product of consecutive even numbers, and one of them must be a multiple of $4$.