Luego de de esta extensa búsqueda de información resolvimos esta contratiempo que presentan muchos de nuestros lectores. Te regalamos la respuesta y nuestro objetivo es resultarte de gran ayuda.
Solución:
Otra definición equivalente de un mod de raíz primitivo $ n $ es (de Wikipedia),
un número $ g $ es un módulo raíz primitivo $ n $ si cada número coprime a $ n $ es congruente con una potencia de $ g $ modulo $ n $
Por ejemplo, $ 3 $ es un módulo raíz primitivo $ 7 $, pero no modulo $ 11 $, porque
Modulo $ 7 $,
$$ 3 ^ 0 equiv1, ; 3 ^ 1 equiv3, ; 3 ^ 2 equiv2, ; 3 ^ 3 equiv6, ; 3 ^ 4 equiv4, ; 3 ^ 5 equiv5, ; 3 ^ 6 equiv1 pmod 7 $$
Y obtuviste todos los resultados posibles: $ 1, 3, 2, 6, 4, 5 $. No puedes conseguir un $ 0 $, pero $ 0 $ no es coprime a $ 7 $, por lo que no es un problema. Por eso $ 3 $ es un módulo raíz primitivo $ 7 $.
Considerando que, módulo $ 11 $,
$$ 3 ^ 0 equiv1, ; 3 ^ 1 equiv3, ; 3 ^ 2 equiv9, ; 3 ^ 3 equiv5, ; 3 ^ 4 equiv4, ; 3 ^ 5 equiv1 pmod 11 $$
Y modulo $ 11 $, solo tienes los valores posibles $ 1, 3, 9, 5, 4 $ y la secuencia comienza a repetirse después $ 3 ^ 5 $, sou nunca obtendrás un $ 3 ^ k equiv2 $, por ejemplo. Por eso $ 3 $ es no un módulo raíz primitivo $ 11 $.
La secuencia $ g ^ k $ siempre está repitiendo módulo $ n $ después de algún valor de $ k $, ya que solo puede tomar un número finito de valores (por lo que al menos un valor aparece al menos dos veces, por ejemplo $ r, s $ y $ r> s $ tú tienes $ g ^ r equiv g ^ s $), y un término depende solo del anterior: $ g ^ k + 1 equiv g cdot g ^ k $. Por lo tanto $ g ^ r + k equiv g ^ s + k $ para todos $ k $.
Si $ g $ y $ n $ son coprime, se vuelve un poco más simple, porque $ g ^ k equiv g ^ k ‘ pmod n $ para algunos $ k, k ‘$ con $ k> k ‘$implica$ g ^ k-k ‘ equiv 1 $ (puede tomar la inversa modular porque entonces todos $ g ^ k $ son coprimeras de $ n $), luego con $ r = k-k ‘$, tú tienes $ g ^ k + r equiv g ^ kg ^ r equiv g ^ k $ para todos $ k $.
Si $ g $ y $ n $ no son coprime, no es tan simple: si$ g ^ r equiv 0 pmod n $ para algunos $ r $ luego $ g ^ k + r equiv g ^ kg ^ r equiv 0 $ para todos $ k $. Pero también puede tener una secuencia repetida sin ningún $ 1 $, por ejemplo, módulo $ 15 $,
$$ 3 ^ 0 equiv1, ; 3 ^ 1 equiv3, ; 3 ^ 2 equiv9, ; 3 ^ 3 equiv12, ; 3 ^ 4 equiv6, ; 3 ^ 5 equiv3 pmod 15 $$
Y comienza a repetirse después $ 3 ^ 4 $, con números no coprime a $ 15 $ ya que $ g = 3 $ no es coprime a $ n $ cualquiera. Y de hecho, si $ g $ y $ n $ no son coprime, nunca obtienes un $ 1 $ otra vez después $ g ^ 0 equiv1 pmod n $, porque todo $ g ^ k $ tener un factor común con $ n $.
Alternativamente, el orden multiplicativo de $ g $ modulo $ n $ es el exponente más pequeño $ k $ tal que $ g ^ k equiv 1 pmod n $.
Aquí ves que el orden multiplicativo de $ 3 $ modulo $ 7 $ es $ 6 $, y el orden multiplicativo de $ 3 $ modulo $ 11 $ es $ 5 $, entonces por tu definición, $ 3 $ es de hecho un módulo raíz primitivo $ 7 $, pero no modulo $ 11 $.
Observe también que el orden multiplicativo de $ g $ modulo a prime $ p $ es siempre menor o igual a $ p-1 $, ya que el pequeño teorema de Fermat establece que para un primo $ p $ y $ a $ no divisible por $ p $, $ a ^ p-1 equiv 1 pmod p $. Entonces el orden multiplicativo también es siempre un divisor de $ p-1 $, y conduce a un algoritmo simple para buscar raíces primitivas:
Para probar un posible $ g $, toma la factorización entera de $ p-1 $, y para cada factor primo $ d $ de $ p-1 $, calcular $ g ^ (p-1) / d $ modulo $ p $. Si ninguno de estos es $ 1 $, luego $ g $ es un módulo raíz primitivo $ p $, ya que $ k = p-1 $ es entonces el mas pequeño $ k $ tal que $ g ^ k equiv 1 pmod p $.
Para grande $ p $ y el uso de exponenciación modular al elevar al cuadrado, es mucho más rápido que calcular todos $ g ^ k $ modulo $ p $ por $ k = 0,1, ldots, p-1 $ y verificar si todos los valores posibles están allí (pero aún necesita una factorización de enteros).
Te estás preguntando sobre el anillo (con estructura aditiva y estructura multiplicativa) $ mathbb Z $ modulo $ n $, a menudo denotado $ mathbb Z / (n) $. Puede sumar y multiplicar módulo $ n $, las operaciones tienen sentido.
Para un $ n $ general (no necesariamente primo), la estructura multiplicativa puede comportarse bastante mal. Por ejemplo, cuando $ n = 8 $, tiene $ 4 cdot2 = 0 $, producto de dos cosas distintas de cero que resultan ser cero. Hay cantidades módulo $ n $ (“residuos mod $ n $”) que tienen recíprocos, sin embargo: para el caso $ n = 15 $, tenemos $ 2 cdot8 = 1 $, módulo $ 15 $. Los residuos que tienen recíprocos se pueden denotar $ ( mathbb Z / (n)) ^ * $ o algo así, y este sistema es una estructura multiplicativa en sí misma, un “grupo multiplicativo”. Debajo ciertas circunstancias, este grupo multiplicativo es “cíclico”, es decir, hay un elemento particular cuyos poderes atraviesan todas las cosas en $ ( mathbb Z / (n)) ^ * $. Por ejemplo, puede comprobar que los elementos de $ ( mathbb Z / (9)) ^ * $ son $ 1,2,4,5,7,8 $, y también puede comprobar que todos de estos es una potencia de dos, módulo nueve. Cuando hay un residuo tan agradable como $ 2 $ aquí, se llama raíz primitiva, y es un teorema serio que cuando $ n $ es un primo, siempre hay una raíz primitiva. Por ejemplo, $ n = 5 $ tiene $ 2 $ para un pr, $ n = 7 $ no puede usar $ 2 $, pero $ 3 $ es un buen pr Hay algunas pautas útiles para encontrar una raíz primitiva, pero yo no quiero ir allí esta noche. El hecho importante es que los únicos números $ n $ que tengo las raíces primitivas módulo $ n $ tienen la forma $ 2 ^ varepsilon p ^ m $, donde $ varepsilon $ es $ 0 $ o $ 1 $, $ p $ es un primo impar y $ m ge0 $
Acuérdate de que puedes optar por la opción de parafrasear .