Take the 2-minute tour ×
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.

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|improve this question

1 Answer 1

up vote 3 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.


Alternatively,

$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|improve this answer

Your Answer

 
discard

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.