Encuentra una raíz primitiva de $71$ .

Question

En mi clase de Teoría de Números encontramos que $7$ era una raíz primitiva de 41 encontrando primero dos enteros que tienen orden $5$ y $8$ $modulo 41$ respectivamente, siendo estos $16$ y $3$ . Desde $16(3)=7(mod41)$ 7 es una raíz primitiva.

Estoy tratando de hacer esto para $71$ y hasta ahora tienen que $5$ tiene orden $5(mod71)$ .

Estoy luchando por encontrar enteros cuyo orden $modulo71$ son $2$ y $7$ .

Answer 1

$G=\mathbb{Z}/(71\mathbb{Z})^*$ es un grupo cíclico de orden $70=2\cdot 5\cdot 7$ . De ello se desprende que cualquier $g\in G$ tal que $g^{10}\not\equiv 1\pmod{71}$ , $g^{14}\not\equiv 1\pmod{71}$ y $g^{35}\not\equiv 1\pmod{71}$ es un generador de $G$ . Hay $\varphi(70)=1\cdot 4\cdot 6=24$ generadores, por lo que un residuo aleatorio no cuadrático es muy probable que sea un generador. $71\equiv -1\pmod{8}$ así que $2$ es un residuo cuadrático. $71\equiv -1\pmod{3}$ así que $3$ es también un residuo cuadrático. $4$ es un cuadrado, por lo tanto un residuo cuadrático. $71\equiv 1\pmod{5}$ Por lo tanto $5$ también es un residuo cuadrático. $6$ también, ya que es el producto de dos residuos cuadráticos ( $2$ y $3$ ). $7$ es el candidato más pequeño razonable para un generador. Tenemos $$ 7^{35}\equiv \left(\frac{7}{71}\right)\stackrel{\text{reciprocity}}{\equiv}-\left(\frac{1}{7}\right)\equiv -1\pmod{71}, $$ $$ 7^5\equiv 51 \equiv -20\pmod{71},$$ $$ 7^{10}\equiv (-20)^2 \equiv 45\pmod{71}, $$ $$ 7^{14}\equiv (-20)^3\cdot 7^{-1} \equiv (-20)^3\cdot(-10) \equiv 54\pmod{71} $$ por lo que $7$ es en realidad un generador.