Solving a non-linear congruence

Question

How would I go about solving the following:

$$x^2+1\equiv2\pmod8$$

I know I can subtract, and I get:

$$x^2\equiv1\pmod8$$

I'm not sure if I am allowed to square root both sides, or if I should employ a different technique?

Answer 1

Rewrite the last relation as $x^2-1\equiv0 \pmod 8$ or equivalently as $$(x-1)(x+1)\equiv0 \pmod 8$$ and assume that $x$ is even, i.e. $x=2n$ for $n \in \mathbb N$. Then $$(x-1)(x+1)=(2n-1)(2n+1)=4n^2-1$$ which cannot be a multiple of $8$.

Now assume that $x$ is odd, i.e. $x=2n+1$ for $n \in \mathbb N$. Then $$(x-1)(x+1)=(2n+1-1)(2n+1+1)=2n(2n+2)=4n(n+1)$$ where either $n$ or $n+1$ must be even. Hence $$4n(n+1) | 8$$ which means that $$(x-1)(x+1)\equiv 0 \pmod 8$$ for every odd $x$.

---

From the last one you have that $$x^2=8k+1$$ which gives $$\begin{array}{rlcl}k=1&&\quad&x^2=9&=3^2\\k=3&=1+2&\quad&x^2=25&=5^2\\k=6&=3+3&\quad&x^2=49&=7^2\\k=10&=6+4&\quad&x^2=81&=9^2\\k=15&=10+5&\quad&x^2=121&=11^2\\...&...&&...&...\end{array}$$ The next $k$ that solve it should be $21, 28, 36, 45, \dots$ with solutions $13^2, 15^2, 17^2, 19^2, \ldots$