Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
up vote 8 down vote accepted

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

share|cite|improve this answer
+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}$.

share|cite|improve this answer

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.

share|cite|improve this 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}$

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.