Mostrar que$233$ divide$2^{29} - 1$

Question

Muestre que$233$ divide$2^{29} - 1$.

Al principio traté de encontrar alguna congruencia trivial con la fuerza bruta en mi camino hacia el exponente 29, sin embargo, parece que solo$2^{29} \equiv 1 \pmod{233} $.

\begin{align} 2^8 &\equiv 23 \pmod{233}\\ 2^{12} &\equiv 135 \pmod{233}\\ 2^{16} &\equiv 63 \pmod{233}\\ 2^{24} &\equiv 51 \pmod{233}\\ 2^{29} &\equiv 1 \pmod{233} \end{align}

¿Hay alguna congruencia inteligente para hacer que esta fuerza bruta sea menos ... bruta o es el pequeño Fermat un deber en esta situación?

Answer 1

Exponenciación al cuadrado es la técnica más habitual. Esto no es tan diferente de lo que hizo. \begin{align*} 2^1 &= 2 \pmod{233} \\ 2^2 &= 4 \pmod{233} \\ 2^4 &= 16 \pmod{233} \\ 2^8 &= 23 \pmod{233} \\ 2^{16} &= 23^2 \cong 23(10 + 10 + 3) \cong -3 -3 +69 \cong 63 \pmod{233} \\ \text{and } 29 &= 16+8+4+1 , \text{ so} \\ 2^{29} &\cong 63 \cdot 23 \cdot 16 \cdot 2 \cong 46\,368 \cong 1 \pmod{233} \\ \end{align*}

Por lo general, no hay ningún atajo conocido para determinar el orden de un elemento de módulo un primo. (Aquí, hemos demostrado que el orden de $2$ mod $233$ divide $29$. Desde $29$ es primo, y el orden de $2$ no $1$, en su orden es $29$.)

Además de la cadena de exponenciación es un método para reducir algunos de los anteriores. Sin embargo, encontrar el mínimo, además de las cadenas es un NP-completo problema, así que tal vez esta no es la mejor opción para el cálculo manual.

Answer 2

El pequeño teorema de Fermat es bastante útil y probablemente sea la forma más fácil de resolver esto. Tenga en cuenta que$233$ es primo y que$29\mid 232$. Particularmente,$\frac{232}{29}=8$ Entonces, por el pequeño teorema de Fermat,

PS

y$$2^{232}\equiv 1\pmod{233}$ debería llevarte a la solución.