Raíz cuadrada de $1 \pmod m$ para $m$ primo y $m$ no primo

Question

Mientras hacía la raíz cuadrada $1$ módulos es decir, $x ^2 \equiv 1 \pmod m$ noté lo siguiente:
Si el módulo $m$ es primo parece que el cuadrado siempre es $1$ y $m - 1$
Pero si no es primo, no es el caso y no estoy seguro si hay una fórmula general para eso.
Ejemplos:
$1 \pmod 3$: $1$ y $2$
$1 \pmod 4$: $1$ y $3$
$1 \pmod 5$: $1$ y $4$
$1 \pmod 6$: $1$ y $5$
$1 \pmod 7$: $1$ y $6$
$1 \pmod 8$: $1$ y $3$ y $5$ y $7$
$1 \pmod 9$: $1$ y $8$
$1 \pmod {11}$: $1$ y $10$

Aquí vemos que para un módulo primo tenemos $1$ y $m - 1$ mientras que para los no primos varía.

¿Estoy en lo correcto al generalizar que para los números primos siempre se cumple esto? ¿Cuál es la propiedad que causa esto y hay una conclusión general para los no primos?

Answer 1

Esquema para una respuesta.

Sea $g(m)$ el número de raíces distintas a $x^2\equiv1\pmod m.$

Si $m,n$ son primos relativos, entonces muestra que $g(mn)=g(m)g(n).$ (Pista: usa el teorema chino del resto.) (Esta propiedad se llama "multiplicativa.")

Esto es cierto para cualquier congruencia polinómica en una variable. Si $h(m)$ es el número de soluciones de $x^3+x\equiv 1\pmod m,$ entonces $h$ es multiplicativa.

---

Por lo tanto, solo necesitamos calcular $g(p^k),$ donde $p$ es un número primo.

Si $p$ es un primo impar, entonces muestra que $g(p^k)=2$ para cualquier $k>0.$

Esto se debe a que $x^2\equiv 1\pmod {p^k},$ significa que $p^k\mid x^2-1=(x-1)(x+1).$ Pero $x-1$ y $x+1$ no pueden ser ambos divisibles por $p,$ por lo que esto significa que $p^k\mid x-1$ o $p^k\mid +1,$ y así $x\equiv\pm 1\pmod{p^k}.$

Si $p=2,$ tienes el problema de que $x-1$ y $x+1$ pueden ser ambos divisibles por $2.$

Muestra que:

$$g(2^k)=\begin{cases}1&k=0,1\\2&k=2\\4&k>2 \end{cases}$$

---

Finalmente, si $$m=2^kp_1^{k_1}p_2^{k_2}\cdots p_{n}^{k_n}$$ con los $p_i$ primos impares distintos, entonces:

$$g(m)=g(2^k)2^n$$

Answer 2

Ok. ¿Sabías que si y solo si $m$ es primo entonces $\mathbb Z/m\mathbb Z$ es un cuerpo?

Un polinomio de grado $n$ sobre un cuerpo tiene como máximo $n$ raíces en ese cuerpo. Así que el polinomio $x^2-1$ puede no tener raíces o tener $2$ raíces (no puede ser que tenga solo $1$ raíz, ya que esto implicaría al factorizar que en realidad tiene dos raíces).

En nuestro caso está claro, las dos raíces son $1$ y $-1=m-1$.

Ahora, si $m=2,4,p^k,2p^k$ para un primo impar $p$, entonces $(\mathbb Z / m\mathbb Z)^\times$ es cíclico, es decir, cada elemento es de la forma $g^l$ para algún generador $g$. Entonces $g^{2l}$ alcanza solo la mitad de los elementos, pero cada uno dos veces (excepto en el caso de $m=2$, donde el grupo multiplicativo solo tiene un elemento).

Así que también en este caso solo obtenemos $1$ y $-1$.

Si $m=2^k$, entonces cualquier raíz tiene que ser una raíz módulo $2$, así que cualquier raíz tiene que ser de la forma $1+2l$. Entonces $$ (1+2l)^2 - 1 = 1 + 4l^2 + 4l - 1 = 4l(l+1) $$ esto solo puede ser $0$ módulo $2^k$ si tanto $l$ como $(l+1)$ son múltiplos de $2^{k-2}$. Dado que solo necesitamos considerar $0\leq l < 2^k$, solo obtenemos estas posibilidades: $0$, $2^{k-2}$, $2^{k-1}$, $3\cdot 2^{k-2}$.

Observa que si $l=2^{k-1}$ o $2^{k-1}-1$ entonces $2l \equiv 2\cdot0$ o $2l\equiv 2\cdot(0-1)$. Así que solo tenemos que contar los casos $0$ y $2^{k-2}$ para $l$ o $l+1$. Esto nos da exactamente cuatro soluciones $1,-1,1+2^{k-1},-1+2^{k-1}$ si $k>2$ (si no, obtenemos 2 soluciones para $k=2$ y una solución para $k=0$).

Así que ahora podemos manejar los casos de todas las potencias de números primos. Así que si $m$ es compuesto, podemos usar el Teorema Chino del Resto para obtener todas las raíces módulo $m$ al obtener todas módulo las potencias de los números primos.

Entonces si $m=2^k p_1^{k_1}p_2^{k_2}\cdots p_n^{k_n}$ para números primos impares $p_i$ entonces tenemos que usar el Teorema Chino del Resto para encontrar $x$ que satisfaga: $$ x\equiv \pm 1\mod p_i^{k_i}$$ y si $k>0$ uno de estos $$ x\equiv 1 \mod 2\qquad \text{si $k=1$} $$ $$ x\equiv \pm 1\mod4 \qquad \text{si $k=2$} $$ $$ x\equiv \pm 1 + \{0,2^{k-1}\} $$ para todas esas combinaciones. Mediante el Teorema Chino del Resto, cada combinación corresponde a una raíz única módulo $m$, así que obtenemos un total de $2^n$ raíces si $k=0,1$, $2^{n+1}$ raíces si $k=2$ y $2^{n+2}$ raíces si $k>2$.

Answer 3

Si $a$ y $b$ son dos enteros positivos coprimos y $$x_1^2\equiv1\pmod{a}\qquad\text{ y }\qquad x_2^2\equiv1\pmod{b},\tag{1}$$ entonces por el teorema del residuo chino existe un entero único $x$ con $0\leq x tal que $$x\equiv x_1\pmod{ab}\qquad\text{ y }\qquad x\equiv x_2\pmod{ab},$$ que consecuentemente satisface $x^2\equiv1\pmod{a}$ y $x^2\equiv1\pmod{b}$, y por lo tanto $$x^2\equiv1\pmod{ab}.\tag{2}$$ Esto muestra que las soluciones a $(2)$ corresponden biyectivamente a pares de soluciones a $(1)$. Así que si $N(m)$ es el número de soluciones a $x^2\equiv1\pmod{m}$, entonces $N(ab)=N(a)N(b)$. Se sigue que si $m$ es un entero positivo que se factoriza como $m=\prod p^{m_p}$, entonces $$N(m)=\prod N(p^{m_p}).$$ Por lo tanto, es suficiente determinar el número de soluciones para todas las potencias primas.

---

Si $m=p$ es un primo y $x^2\equiv1\pmod{p}$ entonces $p$ divide $$x^2-1=(x-1)(x+1),$$ y así $p$ divide $x-1$ o $p$ divide $x+1$, o equivalente, para algún entero $n$ tenemos $$x=np\pm1.$$ Si requerimos que $0\leq x entonces las únicas soluciones son $x=1$ y $x=m-1$. Notar que estas no son distintas solo para $p=2$.

---

De manera similar, si $m=p^k$ es una potencia impar de un primo y $x^2\equiv1\pmod{p^k}$ entonces $p^k$ divide $$x^2-1=(x-1)(x+1).$$ Como los dos factores difieren por $2$ no pueden ambos ser divisibles por $p$, y así $p^k$ divide $x-1$ o $p^k$ divide $x+1$, o equivalente, para algún entero $n$ tenemos $$x=np^k\pm1.$$ Si de nuevo requerimos que $0\leq x entonces las únicas soluciones son $x=1$ y $x=m-1$, y así $N(p^k)=2$.

---

Por otro lado, si $m=2^k$ y $x^2\equiv1\pmod{2^k}$ entonces $2^k$ divide $$x^2-1=(x-1)(x+1).$$ Como los dos factores difieren por $2$ deben ser ambos pares, y no pueden ser divisibles ambos por $4$, y así $2^{k-1}$ divide $x-1$ o $2^{k-1}$ divide $x+1$, o equivalente, para algún entero $n$ tenemos $$x=n2^{k-1}\pm1.$$ Si de nuevo requerimos que $0\leq x<2^k$ entonces las únicas soluciones son $$x=1,\qquad x=2^{k-1}-1,\qquad x=2^{k-1}+1,\qquad x=2^k-1.$$ Notar que para $k=1$ y $k=2$, correspondientes a $m=2$ y $m=4$, esto solo produce $1$ y $2$ soluciones distintas, respectivamente. Esto muestra que $N(2)=1$, $N(4)=2$ y $N(2^k)=4$ para $k\geq3$.