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]${\textstyle a^{k}\ \equiv \ 1{\pmod {n}}}$

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]${\displaystyle \operatorname {ord} _{n}(a)}$

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

${\displaystyle {\begin{array}{llll}4^{0}&=1&=0\times 7+1&\equiv 1{\pmod {7}}\\4^{1}&=4&=0\times 7+4&\equiv 4{\pmod {7}}\\4^{2}&=16&=2\times 7+2&\equiv 2{\pmod {7}}\\4^{3}&=64&=9\times 7+1&\equiv 1{\pmod {7}}\\4^{4}&=256&=36\times 7+4&\equiv 4{\pmod {7}}\\4^{5}&=1024&=146\times 7+2&\equiv 2{\pmod {7}}\\\vdots \end{array}}}$

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.

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 ⁻¹ y podemos multiplicar ambos lados de la congruencia con a ^{− t} , obteniendo a ^{s − t}  ≡ 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 ).

• Máxima CAS  : zn_order (a, n) ^[3]
• Lenguaje Wolfram  : OrdenMultiplicativo[k, n] ^[4]
• Código Rosetta : ejemplos de orden multiplicativo en varios idiomas ^[5]

• Logaritmo discreto
• Aritmética modular

• Niven, Ivan ; Zuckerman, Herbert S.; Montgomery, Hugh L. (1991). Introducción a la teoría de números (quinta edición). John Wiley & Sons . ISBN 0-471-62546-9.

• Weisstein, Eric W. "Orden multiplicativo". MathWorld .