Probando$5^n \equiv 1 \pmod {2^r}$ cuando$n=2^{r-2}$

Question

¿Cómo puedo demostrar que$5^n \equiv 1 (\bmod 2^r$) cuando$n=2^{r-2}$?

En realidad, lo que estoy tratando de probar es que el grupo cíclico generado por la clase de residuo de$5 (\bmod 2^r)$ es de orden$2^{r-2}$.

Answer 1

Podemos dividir el problema original en dos partes. La pregunta específica que usted pidió no tiene nada que ver con $5$ y es contestado por todos los impares $a$$1$. El hecho de que el orden de $5$ se $2^{r-2}$ y no algo más pequeño es demostrado en la Parte $2$.

Parte $1$: Supongamos que $a$ es impar, y $r \ge 3$. A continuación,$a^{2^{r-2}}\equiv 1 \pmod{2^r}$.

Desde $2^r$ no tiene una raíz primitiva, el orden de $a$ modulo $2^r$ es menos de $\varphi(2^r)$. Pero el orden de $a$ divide $\varphi(2^r)$. Desde $\varphi(2^r)=2^{r-1}$, se deduce que el orden de $a$ es un divisor de a$2^{r-1}$, que es menos de $2^{r-1}$. Por lo tanto el orden de $a$ divide $2^{r-2}$. De ello se desprende que $a^{2^{r-2}}\equiv 1 \pmod{2^r}$.

Parte $2$: Nos muestran que si $r\ge 3$,$5^{2^{r-3}}\not\equiv 1 \pmod{2^r}$. Esto demuestra que el orden de $5$ modulo $2^r$ se $2^{r-2}$, y no es algo menor.

Se demuestra por inducción que $5^{2^{r-3}}\equiv 1+2^{r-1} \pmod{2^r}$, y así, en particular,$5^{2^{r-3}}\not\equiv 1 \pmod{2^r}$.

Es fácil comprobar que el resultado se da en $r=3$. Supongamos ahora que $5^{2^{k-3}}\equiv 1+2^{k-1} \pmod{2^k}$. Nos muestran que $5^{2^{k-2}}\equiv 1+2^{k} \pmod{2^{k+1}}$.

Por la hipótesis de inducción $5^{2^{k-3}}= 1+2^{k-1} +s2^k$ algunos $s$. Plaza de los dos lados, y simplificar el modulo $2^{k+1}$. Tenemos que $$5^{2^{k-2}}=(1+2^{k-1} +s2^k)^2 \equiv 1+2^k +2^{2k-2}\pmod{2^{k+1}}.$$ Pero $2^{2k-2}$ es divisible por $2^{k+1}$, ya que el $k \ge 3$. El resultado de la siguiente manera.

Answer 2

Sugerencia: $$ 5 ^ {2 ^ {k +1}} - 1 = (5 ^ {2 ^ k} -1) (5 ^ {2 ^ k} +1) $$ El último factor siempre es congruente con$2\pmod 4$. Recomiendo que luego demuestres un resultado que dé la potencia exacta de dos que divide$5^{2^n}-1$ por inducción en$n$. Esto le da el orden de la clase de residuo de$5$ modulo cualquier potencia de dos.

Answer 3

Sugerencia: si$a=1\pmod{2b}$ entonces$a^2=1\pmod{4b}$.

(Prueba: si$a=2bk+1$ entonces$a^2=4bk(bk+1)+1$. Fin de la prueba.)

Use esto para$a=5^n$,$n=2^{r-2}$ y$b=2^{r-1}$, para crear una prueba por inducción en$r$, comenzando desde el$r=2$ caso$5^1=1\pmod{4}$.

Answer 4

Sea un entero impar = 2b +1 (por ejemplo),$$a^2=4b^2+4b+1=8b(b+1)/2+1=8c+1 $$(say) where $$c=b(b+1)/2$$ an integer (See also If $ n$ is an odd natural number, then $ 8$ divides $ n ^ {2 } -1 $)$$a^4=(1+8c)^2=1+16c+64c^2=1+16d $$ for some integer $$d=c+4c^2$ $$$a^8=(1+16d)^2=1+32d+256d^2=1+32e$ $ Usando la inducción para n≥3, obtenemos$$a^{2^{n-2}}≡1(mod 2^n).$ $ Vea http: //www.amazon .com / Introducción-Teoría-Números-Ivan-Niven / dp / 0471625469