Encuentra todas las raíces primitivas de $13$

Question

Encuentra todas las raíces primitivas de $13$

Mi intento:

Desde entonces $13$ es un primo que tengo que buscar $g$ tal que $g^{13-1}\equiv 1\pmod{13}$

Hay $\phi(12)=4$ clases modulo $12$

¿cómo puedo encontrar las clases?

Answer 1

Claramente, $2$ es una raíz primitiva $\pmod{13}$

como $2^n\not\equiv1\pmod{13}$ para $1\le n<12$

Ahora usa el orden $_ma=d, $ ord $_m(a^k)=\dfrac{d}{(d,k)}$ ( Prueba @Page#95)

Aquí $d=\phi(13)=?$ y necesitamos a ord $_m(a^k)=d$ que necesita $(d,k)=1$

Answer 2

Toma todos los números menores y coprimos a 13 . Del 1 al 12 son coprimos del 13 . Comprueba $1^{13-1}\equiv 1\pmod{13}$ $2^{13-1}\equiv 1\pmod{13}$ Y así hasta $12^{13-1}\equiv 1\pmod{13}$ Cada 1 a 12 que es $\equiv 1\pmod{13}$ es la respuesta requerida . $edit $ La potencia debe ser la menor que dé el valor $\equiv 1\pmod{13}$

Answer 3

Mi método rápido y sucio fue observar que $13-1=12$ tiene factores primos $2,3$ & encontrar rápidamente los cuadrados y cubos de un número, ya que éstos no pueden ser raíces primitivas, y no comprobar los que ya han aparecido. Cualquier indicación de un "ciclo corto" (como $5$ ) también se descarta inmediatamente.

$2: 2^2 \equiv 4, 2^3 \equiv 8 \\ 3: 3^2 \equiv 9, 3^3 \equiv 1 \text{(discard all)}\\ 5: 5^2 \equiv 12 \equiv -1 \text{(discard all)} \\ 6: 6^2 \equiv 10, 6^3 \equiv 8 \\ 7: 7^2 \equiv 10, 7^3 \equiv 5 \\ 11: 11^2 \equiv 4, 11^3 \equiv 5 $

saliendo de $\{2,6,7,11\}$ como las raíces primitivas, lo que concuerda con la expectativa de $\phi(12)=4$ raíces (y también el conocimiento de que para cada raíz primitiva $g \bmod p$ , $-g$ es una raíz primitiva si $p \equiv 1 \bmod 4$ ).

Answer 4

Los primos no tienen sólo una raíz primitiva, sino muchas. Así que se encuentra la primera raíz primitiva tomando cualquier número, calculando sus potencias hasta que el resultado sea 1, y si p = 13 hay que tener 12 potencias diferentes hasta que el resultado sea 1 para tener una raíz primitiva.

Si has probado un número a que no era una raíz primitiva, entonces no pruebes sus potencias sino algún otro número.

Una vez que tengas una raíz primitiva, llámala g. $g^2$ no es una raíz primitiva porque $(g^2)^6 = g^{12} = 1$ . Lo mismo para las potencias 3, 4, 6, 8, 9, 10. $g^5$ , $g^7$ , $g^11$ son las otras raíces primitivas.