$x^2 \equiv 2x \pmod m$

Question

Para contar las soluciones para la congruencia$x^2 \equiv 2x \pmod n$, si escribimos$m$ como$m = p_1^{a_1}p_2^{a_2}...p_r^{a_r}$ tenemos el siguiente sistema equivalente de ecuaciones de congruencia:

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

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

. . .

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

Estoy pensando en los dos casos de las relaciones de$x$ y$x-2$ donde

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

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

y considere la cantidad de soluciones para cada caso. ¿Estoy en el camino correcto?

Answer 1

Mediante su enfoque, vamos a por el primer $p,$ $p\mid x$ y $p\mid (x-2)$

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

Así, si el primer $p>3,$ $p^n\mid x$ o $p^n\mid (x-2)$

Por lo tanto, hay $2$ in-congruente soluciones, es decir, $0,2\pmod {p^n}$$x^2\equiv2x \pmod {p^n}$.

Si el caso de $p=2,x$ debe ser $\implies (x,x-2)=2\implies(\frac x2,\frac{x-2}2)=1$

Por eso, $2^n\mid x(x-2)\implies 2^{n-2}\mid \frac x2\cdot\frac{(x-2)}2$ si $n\ge 3$

Así que, o bien $2^{n-2}\mid \frac x2$ o $2^{n-2}\mid \frac{(x-2)}2$

Por eso, $x\equiv0,2 \pmod{2^{n-1}}\implies x\equiv0,0+2^{n-1},2,2+2^{n-1}\pmod{2^n}$ es decir, hay $4$ in-congruente soluciones.

Si $n=2, x(x-2)\equiv 0\pmod4\implies x\equiv0,2\pmod4$ es decir, $2$ in-congruente soluciones.

Si $n=1, x(x-2)\equiv 1\pmod2\implies x\equiv 1\pmod2$ es decir, exactamente $1$ in-congruente solución.

Ahora, si $ax^2+bx+c\equiv 0\pmod {m_1}$ $ax^2+bx+c\equiv 0\pmod {m_2}$ ha $t_1,t_2$ soluciones respectivamente(donde $(m_1,m_2)=1$),

$ax^2+bx+c\equiv 0\pmod {m_1\cdot m_2}$ tienen $t_1\cdot t_2$ soluciones.

---

Alternativamente,

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

Si $y^2\equiv1 \pmod {q^n}$ donde prime $q>2$

Por eso, $q^n \mid (y-1)(y+1)$ pero $(y-1,y+1)\mid 2$

cualquiera de las $q^n\mid (y-1)$ o $q^n\mid (y+1)$

Por lo tanto, hay $2$ in-congruente soluciones, es decir, $y\equiv \pm 1\pmod {q^n}$$y^2\equiv1 \pmod {q^n}$.

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

por eso, $2^n\mid (y-1)(y+1)$ aquí $(y-1,y+1)=2$ $y$ es impar.

por eso, $2^{n-2} \mid\frac{(y-1)}2\cdot\frac{(y+1)}2$ donde $(\frac{y-1}2,\frac{y+1}2)=1$ si $n\ge 3$

así que, o bien $2^{n-1}\mid (y-1)$ o $2^{n-1}\mid (y+1)$

Por lo tanto, hay $2$ in-congruente soluciones, es decir, $y\equiv \pm 1\pmod {2^{n-1}}$

Por lo tanto, habrá de ser $4$ in-congruente soluciones, es decir, $y\equiv \pm 1,2^{n-1}\pm1\pmod {2^n}$

Si $n=2, y^2\equiv 1\pmod4\implies y\equiv\pm 1\pmod4$ es decir, $2$ in-congruente soluciones.

Si $n=1, y^2\equiv 1\pmod2\implies y\equiv 1\pmod2$ es decir, exactamente $1$ in-congruente solución.