En la teoría de números , dado un número entero positivo n y un número entero un primos entre sí a n , la orden multiplicativo de un módulo n es el más pequeño número entero positivo k tal que. [1]
En otras palabras, el orden multiplicativo de un 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 números enteros módulo n , podemos demostrar que a en realidad tiene un orden al señalar 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 de casillero debe haber dos potencias, digamos s y t , y sin pérdida de generalidad s > t , de tal manera que un s ≡ un t (mod n ). Dado que a y n son coprimos , esto implica que a tiene un elemento inverso a −1 y podemos multiplicar ambos lados de la congruencia con a - t , lo que da como resultado a s - t ≡ 1 (mod n ).
El concepto de orden multiplicativo es un caso especial del orden de los elementos del grupo . El orden multiplicativo de un número de un módulo n es el orden de una en el grupo multiplicativo cuyos elementos son los residuos modulo n de los números coprimo con n , y cuyo grupo de operación es la multiplicación modulo 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 λ ( n ), un valor de la función de Carmichael , que es un enunciado aún más fuerte que la divisibilidad de φ ( n ).
Lenguajes de programación
- CAS máximo: zn_order (a, n) [3]
- Código Rosetta : ejemplos de orden multiplicativo en varios idiomas [4]
Ver también
Referencias
- ^ Niven, Zuckerman & Montgomery 1991 , Sección 2.8 Definición 2.6
- ↑ von zur Gathen, Joachim ; Gerhard, Jürgen (2013). Álgebra informática moderna (3ª ed.). Prensa de la Universidad de Cambridge. Sección 18.1. ISBN 9781107039032.
- ^ Manual de Maxima 5.42.0: zn_order
- ^ rosettacode.org - ejemplos de orden multiplicativo en varios idiomas
- Niven, Ivan ; Zuckerman, Herbert S .; Montgomery, Hugh L. (1991). Introducción a la teoría de los números (5ª ed.). John Wiley e hijos . ISBN 0-471-62546-9.
enlaces externos
- Weisstein, Eric W. "Orden multiplicativo" . MathWorld .