What is the solution for $(x^2- 1) \bmod 8= 0$

Question

I could not figure out the solution of $(x^2- 1) \bmod 8= 0$ Thank you.

Answer 1

There are only $8$ possibilities. Counting with $a^2=(-a)^2$ for all numbers $a$, it can be reduced to $5$. $$0^2=0\equiv 0,\quad (\pm 1)^2=1\equiv 1, \quad (\pm 2)^2=?,\quad (\pm 3)^2=?,\quad 4^2=16\equiv 0 \pmod 8.$$

Answer 2

If $2^{3+n}\mid (x^2-1)$ where $n\ge 0$

Clearly, $x$ is odd and $2^{n+1}\mid\left(\frac{x+1}2\right)\left(\frac{x-1}2\right) $

We know using Bézout's Identity, $\left(\frac{x+1}2,\frac{x-1}2\right)\mid\left(A \frac{x+1}2+B\frac{x-1}2\right)$ where $A,B$ are integers.

But $\frac{x+1}2-\frac{x-1}2=1,$ putting $A=1,B=-1$
so $(\frac{x+1}2,\frac{x-1}2)\mid 1\implies (\frac{x+1}2,\frac{x-1}2)=1$

So, either $2^{n+1}\mid\frac{x-1}2$ or $2^{n+1}\mid\frac{x+1}2$

(a)If $2^{n+1}\mid\frac{x-1}2, 2^{n+2}\mid(x-1),x\equiv1\pmod {2^{n+2}},x=1+a2^{n+2}$ where $a$ is any integer.

If $1+a_12^{n+2}\equiv1+a_22^{n+2}\pmod {2^{n+3}}\iff a_1\equiv a_2\pmod 2$

If $a$ is even $=2b$(say,) $x=1+(2b)2^{n+2}\equiv1\pmod {2^{n+3}}$

If $a$ is odd $=2c+1$(say,) $x=1+(2c+1)2^{n+2}\equiv1+2^{n+2}\pmod {2^{n+3}}$

(b)Similarly, if $2^{n+1}\mid\frac{x+1}2$ we shall get two solutions namely, $-1,2^{n+2}-1\pmod {2^{n+3}}$

So, there will be $4$ in-cogruent solutions $\pmod {2^{n+3}}$

Answer 3

Let $(x^2-1)\equiv0\pmod{2^k}$ with $k\geq3$, i.e. $x^2-1=2^kn$ for some $n$.

We have $2^kn=x^2-1=(x+1)(x-1)$. Since the left-hand side is even and the numbers on the right-hand side have the same oddity, they are both even. At the same time, they differ by $2$ so the number $4$ divides only one of them.

Therefore they are of the form $\{x+1,x-1\}=\{n_1,2^kn_2\}$ or $\{2n_1,2^{k-1}n_2\}$, where $n=n_1n_2$ is some factorization of $n$. From this, we have $x=2^{k-1}m\pm1$ where $m$ is some integer. Four of them are in the interval $[0,2^k)$:

$$1, 2^{k-1}-1, 2^{k-1}+1, 2^k-1.$$

Easy calculation shows that all these really solve the equation. For the case $k=3$ this gives $x\equiv1,3,5,7 \pmod8$.