<s>[INST] Solve the following equivalency $$n^2 \equiv 2 \pmod{9}$$
I don't even know where to begin. Can you provide a step-by-step solution?
Some people seem to solve them as if they were regular equations. So, is $n^2 \equiv 2 \pmod{9}$? I've seen people do this:
$$2n \equiv 2 \pmod{9}$$
$$n \equiv 1 \pmod{9}$$
 [/INST] Let us recall what it means by writing $$a \equiv b \pmod{c}$$ This means that $c \vert (a-b)$. Hence, for instance, $$8 \equiv 3 \pmod{5},\,\,16 \equiv -5\pmod{7}$$
Let us first solve a simple problem $$(2n+1) \equiv 3 \pmod{5}$$ i.e. we want to find $n$ such that $5 \vert (2n+1-3) \implies 5 \vert (2n-2) \implies 5 \vert 2(n-1)$. Since $\gcd(5,2) = 1$, we can conclude that $5 \vert (n-1)$. Hence, the solution is given by$$n \equiv 1 \pmod{5}$$
A nice property is that if $a \equiv b \pmod{c}$, then $a^2 \equiv b^2 \pmod{c}$. What the above statement means is that if $c \vert (a-b)$, then $c \vert (a^2- b^2)$. This is true since $a^2- b^2 = (a-b)(a+b)$ and since $c \vert (a-b)$, $c \vert (a-b)(a+b)$. Hence, $c \vert(a^2-b^2)$.
Let us now look at your problem. We want to find all $n$ such that
$$n^2 \equiv 2 \pmod{9}$$
i.e. we want to find $n$ such that $9 \vert (n^2-2)$. A simple way is to proceed as follows. Any $n$ can be written as $$n \equiv 0,\pm1,\pm2,\pm3,\pm4 \pmod{4}$$ This means that
\begin{align}
n^2 &\equiv 0,(\pm1)^2,(\pm2)^2,(\pm3)^2,(\pm4)^2 \pmod{4}\\
& \equiv 0,1,4,9,16 \pmod{9}\\
& \equiv 0,1,4,0,7 \pmod{9}\\
& \equiv 0,1,4,7 \pmod{9}
\end{align}
But you want to find $n$ such that $n^2 \equiv 2 \pmod{9}$. Hence, there is no solution since
$n^2$ is always $\equiv 0\pmod{9}$ or $\equiv 1\pmod{9}$ or $\equiv 4\pmod{9}$ or $\equiv 7\pmod{9}$
</s>