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?

$\endgroup$
0

1 Answer 1

4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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