Primaria de la prueba: Si x es una ecuación cuadrática de residuos mod p, entonces es una ecuación cuadrática de residuos mod p^k

Question

En el artículo resolver congruencias de segundo grado, se muestra cómo utilizar Hensel del lema iterativa construir soluciones a a $x^2 \equiv a \pmod{p^k}$ a partir de las soluciones a $x^2 \equiv a \pmod{p}$. En el caso de que $p=2$ es tratada por separado.

Mientras que la construcción es elegante, es un poco largo y su dependencia de la Hensel del lema hace un poco lejos de la escuela elemental a la teoría de números.

Si sólo estamos interesados en una verdadera prueba (en lugar de una constructiva), se puede simplificar la prueba? Es decir, es posible sucintamente a probar el siguiente teorema sin recurrir a Hensel del lema?

Para cualquier prime $p$ y cualquier $k \in \mathbb{N}$ si $x$ es una ecuación cuadrática de residuos de mod $p$, entonces es una ecuación cuadrática de residuos de mod $p^k$.

Answer 1

Damos un recuento de argumento. Deje $p$ ser un extraño prime, y supongamos que $a$ no es divisible por $p$. Entonces la congruencia $x^2\equiv a\pmod{p^k}$ no tiene solución o dos soluciones.

Para demostrarlo, supongamos $b^2\equiv a\pmod{p}$. Luego de $x^2\equiv b^2\pmod{p^k}$ llegamos a la conclusión de que $p^k$ divide $(x-b)(x+b)$. Desde $p$ no se puede dividir tanto, llegamos a la conclusión de que $p^k$ se divide una de $x-b$ o $x+b$. Así que si la congruencia tiene al menos una solución de $b$, tiene exactamente dos, a saber:$b$$-b$.

La función de $f(x)=x^2$ (modulo $p^k$) asigna el conjunto de $H$ de los números entre el $1$ $p^k-1$ que no son divisibles por $p$$H$. Por lo anterior, esta función es de dos a uno.

Así que la mitad de los elementos de $H$ QR de $p^k$, y la mitad no lo son. Que la mitad? Los congruente a un residuo cuadrático módulo $p$. Por si $a$ no es un cuadrado modulo $p$, no puede ser un cuadrado modulo $p^k$.

El argumento anterior demuestra que para los impares primos $p$, cada residuo cuadrático módulo $p$ es un residuo cuadrático módulo $p^k$. El resultado no se cumple para $p=2$: tenga en cuenta que $3$ es un residuo cuadrático de $2$, pero no de $4$.

Answer 2

Siempre he apreciado este resultado en LeVeque los Fundamentos de la Teoría de números, el Teorema 4.4:

Supongamos $p$ es un alojamiento relativamente primer a $a$. Deje $t_n$ ser el orden de $a$ modulo $p^n$ y asumir que $p^z$ divide exactamente $a^{t_1} - 1$. Entonces si $p > 2$ o $z > 1$,

$$t_n = \begin{cases} t_1, \quad &\text{for $n \leq z$}\\\\ t_1 p^{n-z}, \quad &\text{for $n > z$.}\end{cases}$$

Este resultado puede ser utilizado para probar varias congruencias mod de una fuente primaria de energía que de otro modo desordenado y molesto para probar (por ejemplo, ver Otras maneras de deducir la Ciclicidad de las Unidades de ciertos grupos?).

En su pregunta, si $a$ es un residuo cuadrático módulo $p$, $t_1$ divide $\frac{p-1}{2}$. Así, en ambos de los casos anteriores, $t_n$ es un divisor de a $p^{n-1} \cdot\frac{p-1}{2} = \phi(p^n)/2$, lo $a$ es un residuo cuadrático módulo $p^n$.

Answer 3

Supongamos $x^2 \equiv a \mod p$ donde $a \not\equiv 0 \mod p$, e $p$ es una extraña prime. A continuación, $x^2 \equiv a + m p \mod p^2$ algunos $m$. Ahora si $y = x + z p$, $y^2 \equiv x^2 + 2 x z p \equiv a + (m + 2 x z) p \mod p^2$. Por tanto, lo que necesitamos es $m + 2 x z \equiv 0 \mod p$. Pero $2x$ es invertible mod $p$, por lo que sólo toma $z \equiv m (2 x)^{-1} \mod p$.