# 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}$$

-

There are no solutions, since $n^2\equiv 2\pmod{9}$ implies $n^2\equiv 2\pmod{3}$ but $2$ is not a quadratic residue $\pmod{3}$.

-
+1 As simple, short and straight as possible. Nice. – DonAntonio Oct 28 '12 at 17:13
But I am not sure if this is at the level the OP can understand. – user17762 Oct 28 '12 at 17:23

For a small modulus it is easy to check each case

n   n^2 n^2 mod 9
0    0     0
1    1     1
2    4     4
3    9     0
4   16     7
5   25     7
6   36     0
7   49     4
8   64     1


So there are no solutions to $n^2 \equiv 2 \pmod{9}$.

-

The question asks the following. Find all numbers $n$ such that when you divide $n^2$ by $9$, you get a remainder of $2$.

If two numbers $a$ and $b$ differ by a multiple of $9$, then $a^2$ and $b^2$ have the same remainder on division by $9$. So you need only examine the candidates $n=0$, $n=1$, and so on up to $n=8$. Thus, effectively there is a smallish number of candidates. We might as well examine them all.

Try $n=0$. Then $n^2=0$. The remainder on division by $9$ is $0$, not $2$.

Try $n=1$. Then $n^2=1$. The remainder on division by $9$ is $1$, not $2$.

Try $n=2$. Then $n^2=4$. The remainder on division by $9$ is $4$, not $2$.

Try $n=3$. Then $n^2=9$. The remainder on division by $9$ is $0$, not $2$.

Try $n=4$. Then $n^2=16$. The remainder on division by $9$ is $7$, not $2$.

Continue calculating. You will find that the remainder is never equal to $2$.

There are shortcuts. For example, look at $(9-x)^2=81-18x+x^2$. This has the same remainder on division by $9$ as $x^2$. The numbers $n$ that I have not made explicit calculations for above are $n=9-4$, $9-3$, $9-2$, and $9-1$. Since we have checked that $4$, $3$, $2$, and $1$ don't work, we know without calculating that $5$, $6$, $7$, and $8$ can't work.

If instead of $9$ we had a largish number like $105$, we would certainly not want to examine, one by one, all possibilities. In that case the very nice approach by Jack D'Aurizio would lead us very quickly to the answer.

-

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}$

-

Put $\rm\:p=3\:$ in: $\rm\ p^2\:|\:n^2\!+1\!-\!p\:\Rightarrow\:p\:|\:n^2\!+1\:\Rightarrow\:p\equiv1\pmod 4,\:$ since, otherwise, recall

$$\rm mod\ p = 4k\!+\!3\!:\,\ n^2 \equiv -1 \;\Rightarrow\; n^{p-1} \equiv (n^2)^{2k+1}\equiv -1,\,\ contra\ little\ Fermat$$

-