4
$\begingroup$

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?

1 Answers 1

4

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.