stringtranslate.com

Orden multiplicativo

En teoría de números , dado un entero positivo n y un entero a coprimo con n , el orden multiplicativo de a módulo n es el entero positivo más pequeño k tal que . [1]

En otras palabras, el orden multiplicativo de a módulo n es el orden de a en el grupo multiplicativo de las unidades en el anillo de los números enteros módulo n .

El orden de un módulo n a veces se escribe como . [2]

Ejemplo

Las potencias de 4 módulo 7 son las siguientes:

El entero positivo más pequeño k tal que 4 k ≡ 1 (mod 7) es 3, por lo que el orden de 4 (mod 7) es 3.

Propiedades

Incluso sin saber que estamos trabajando en el grupo multiplicativo de los números enteros módulo n , podemos demostrar que a en realidad tiene un orden al notar que las potencias de a solo pueden tomar un número finito de valores diferentes módulo n , por lo que de acuerdo con el principio del palomar debe haber dos potencias, digamos s y t y sin pérdida de generalidad s  >  t , tales que a s  ≡  a t  (mod  n ). Como a y n son coprimos , a tiene un elemento inverso a −1 y podemos multiplicar ambos lados de la congruencia con a t , obteniendo a st  ≡ 1 (mod  n ).

El concepto de orden multiplicativo es un caso especial del orden de los elementos de un grupo . El orden multiplicativo de un número a módulo n es el orden de a en el grupo multiplicativo cuyos elementos son los residuos módulo n de los números coprimos con n , y cuya operación de grupo es la multiplicación módulo  n . Este es el grupo de unidades del anillo Z n ; tiene φ ( n ) elementos, siendo φ la función totiente de Euler , y se denota como U ( n ) o  U ( Z n ).

Como consecuencia del teorema de Lagrange , el orden de a (mod n ) siempre divide a φ ( n ). Si el orden de a es en realidad igual a φ ( n ), y por lo tanto tan grande como sea posible, entonces a se denomina raíz primitiva módulo n . Esto significa que el grupo U ( n ) es cíclico y la clase de residuo de a lo genera .

El orden de a (mod n ) también divide a λ( n ), un valor de la función de Carmichael , lo cual es una afirmación aún más fuerte que la divisibilidad de  φ ( n ).

Lenguajes de programación

Véase también

Referencias

  1. ^ Niven, Zuckerman y Montgomery 1991, Sección 2.8 Definición 2.6
  2. ^ von zur Gathen, Joaquín ; Gerhard, Jürgen (2013). Álgebra informática moderna (3ª ed.). Prensa de la Universidad de Cambridge. Sección 18.1. ISBN  9781107039032.
  3. ^ Manual de Maxima 5.42.0: zn_order
  4. ^ Documentación de Wolfram Language
  5. ^ rosettacode.org - ejemplos de orden multiplicativo en varios idiomas

Enlaces externos