Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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

Toward counting the solutions for the congruence $x^2 \equiv 2x \pmod n$, if we write $m$ as $m = p_1^{a_1}p_2^{a_2}...p_r^{a_r}$ we have the following equivalent system of congruence equations:

$p_1^{a_1}\mid x(x-2)$

$p_2^{a_2}\mid x(x-2)$

. . .

$p_r^{a_r}\mid x(x-2)$

I am thinking of the two cases of the relationships of $x$ and $x-2$ where

  1. $gcd(x,x-2) = 1$

  2. $gcd(x,x-2) = 2$

and consider the number of solutions for each case. Am I on the right track?

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

Using your approach, let for prime $p,$ $p\mid x$ and $p\mid (x-2)$

$\implies p$ divides $x-(x-2)=2\implies p=2$ for $p^n\mid x(x-2)$

So, if prime $p>3,$ either $p^n\mid x$ or $p^n\mid (x-2)$

So, there are $2$ in-congruent solutions, namely, $0,2\pmod {p^n}$ of $x^2\equiv2x \pmod {p^n}$.

If case $p=2,x$ must be even $\implies (x,x-2)=2\implies(\frac x2,\frac{x-2}2)=1$

So, $2^n\mid x(x-2)\implies 2^{n-2}\mid \frac x2\cdot\frac{(x-2)}2$ if $n\ge 3$

So, either $2^{n-2}\mid \frac x2$ or $2^{n-2}\mid \frac{(x-2)}2$

So, $x\equiv0,2 \pmod{2^{n-1}}\implies x\equiv0,0+2^{n-1},2,2+2^{n-1}\pmod{2^n}$ i.e., there are $4$ in-congruent solutions.

If $n=2, x(x-2)\equiv 0\pmod4\implies x\equiv0,2\pmod4$ i.e., $2$ in-congruent solutions.

If $n=1, x(x-2)\equiv 1\pmod2\implies x\equiv 1\pmod2$ i.e., exactly $1$ in-congruent solution.

Now, if $ax^2+bx+c\equiv 0\pmod {m_1}$ and $ax^2+bx+c\equiv 0\pmod {m_2}$ have $t_1,t_2$ solutions respectively(where $(m_1,m_2)=1$),

$ax^2+bx+c\equiv 0\pmod {m_1\cdot m_2}$ will have $t_1\cdot t_2$ solutions.


$x^2\equiv2x\pmod n\implies (x-1)^2\equiv 1\pmod n\implies y^2\equiv1$ if $y=x-1$

If $y^2\equiv1 \pmod {q^n}$ where prime $q>2$

So, $q^n \mid (y-1)(y+1)$ but $(y-1,y+1)\mid 2$

either $q^n\mid (y-1)$ or $q^n\mid (y+1)$

So, there are $2$ in-congruent solutions, namely, $y\equiv \pm 1\pmod {q^n}$ of $y^2\equiv1 \pmod {q^n}$.

If $y^2\equiv1 \pmod {2^n}$,

so, $2^n\mid (y-1)(y+1)$ ,here $(y-1,y+1)=2$ as $y$ is odd.

so, $2^{n-2} \mid\frac{(y-1)}2\cdot\frac{(y+1)}2$ where $(\frac{y-1}2,\frac{y+1}2)=1$ if $n\ge 3$

so, either $2^{n-1}\mid (y-1)$ or $2^{n-1}\mid (y+1)$

So, there are $2$ in-congruent solutions, namely, $y\equiv \pm 1\pmod {2^{n-1}}$

So, there will be $4$ in-congruent solutions, namely, $y\equiv \pm 1,2^{n-1}\pm1\pmod {2^n}$

If $n=2, y^2\equiv 1\pmod4\implies y\equiv\pm 1\pmod4$ i.e., $2$ in-congruent solutions.

If $n=1, y^2\equiv 1\pmod2\implies y\equiv 1\pmod2$ i.e., exactly $1$ in-congruent solution.

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.