4 votos

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

¿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}$.

3voto

Oli Puntos 89

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.

2voto

Did Puntos 1

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}$.

2voto

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.

0voto

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by: