Explica por qué 67 es primo basándote en que el orden de 2 mod 67 es 66

Question

Sin usar el hecho de que 67 es primo, demuestre que el orden de 2 mod 67 es 66 . Explica por qué este resultado demuestra que 67 es primo

Lo que yo entiendo:

• El orden de 2 en $\mathbb{Z}_{67}$ (o mod $67$ ) $ = 66$ significa que $66$ es la potencia más pequeña $2^x$ tal que $2^x \equiv 1$ mod 67

• La prueba de primalidad de Lucas establece si podemos encontrar $a$ tal que $a$ tiene orden $n-1$ mod $n$ entonces $n$ es primo. Aquí la pregunta dice que $a = 2$ tiene orden $67-1=66$

• Este resultado demuestra $67$ es primo por la prueba de Lucas

Ahora la parte que no entiendo es cómo se puede mostrar el orden de $2$ mod $67$ es realmente $66$ ?

Answer 1

Calcular, utilizando el método binario para la exponenciación, y reduciendo en módulo $67$ a menudo. Puede hacerse con una simple calculadora.

Primero verifique que $2^{66}\equiv 1\pmod{67}$ .

Así, el orden de $2$ debe dividir $66$ . Eso deja no muchos números para descartar como el orden de $2$ .

Answer 2

El método de fuerza bruta consiste en calcular $2,2^2,2^3,\dots$ , todo módulo 67, hasta obtener 1, y observe que esto no ocurre hasta llegar a $2^{66}$ .

Puede ahorrarse trabajo calculando primero $2^{66}$ módulo 67 de una manera inteligente (que no requiere calcular primero todas las potencias inferiores), y luego mostrando para todos los primos $p$ dividiendo 66 (a saber, 2, 3 y 11) que $2^{66/p}$ no es 1 módulo 67.

Answer 3

$2^6\equiv64\pmod {67} \implies 2^6\equiv -3 \pmod {67}\implies {(2^6)}^{11}\equiv -3^{11}\pmod {67}$

Ahora, $3^4\equiv 14\pmod {67}\implies 3^8\equiv 196\pmod {67}\equiv{-5}\pmod {67}$

$\implies 3^{11}=3^8.3^3\equiv -135\pmod {67}$

Por lo tanto, $2^{66}\pmod {67}\equiv-3^{11}\pmod {67}\equiv 135\pmod {67}\equiv 1\pmod {67}$

orden de $2$ debe dividir $66=2*3*11$

Factores de $66$ son: $2,3,6,11,22,33,66$

Desde entonces, $2^2=4\not\equiv1\pmod {67}$ , $2^3=8\not\equiv 1 \pmod {67}$ , $2^6=64\equiv{-3}\pmod {67}$ , $2^{11}=38\not\equiv 1\pmod {67}$ , $2^{22}={(2^6)}^3.2^4\equiv{-30}\pmod {67}$ y $2^{33}=2^{22}.2^{11}\equiv{-1}\pmod {67}$

Por lo tanto, el orden de $2\pmod {67}$ es $66$