Órdenes y residuos cuadráticos · Definición

Orden multiplicativo

teoría de números elementalórdenes y residuos cuadráticos

Antes de empezar necesitas conocer

Muchas preguntas sobre potencias en aritmética modular se reducen a saber cuántas veces hay que elevar un número para volver a 1. Este concepto es la base de las raíces primitivas.

Definición

El orden multiplicativo de \( a \) módulo \( n \), \( \operatorname{ord}_n(a) \), es el menor exponente positivo que devuelve a la unidad módulo \( n \).

\[\operatorname{ord}_n(a)=\min\{k\ge 1: a^k\equiv 1 \pmod{n}\}\]

Si \( \operatorname{ord}_n(a)=k \), entonces \( a^m \equiv 1 \pmod{n} \) si y solo si \( k \mid m \). De ahí se sigue que el orden siempre divide a \( \varphi(n) \), que es el contenido del teorema de Euler visto desde el orden.

Para \( n=7 \) y \( a=2 \), las potencias son \( 2, 4, 1 \), así que \( \operatorname{ord}_7(2)=3 \). Este valor es compatible con \( \varphi(7)=6 \), porque 3 divide a 6.

Un error típico es suponer que el orden de cualquier \( a \) coincide con \( \varphi(n) \). El caso \( \operatorname{ord}_7(2)=3 \) ya lo desmiente, y además el orden no existe si \( \gcd(a,n)>1 \).

Para pensar

Si \( \operatorname{ord}_n(a)=k \), ¿qué exponentes \( m \) cumplen \( a^m \equiv 1 \pmod{n} \)?

Exactamente los múltiplos de \( k \), es decir, los \( m \) con \( k \mid m \).

Ejercicios 10

  1. ¿Cuál es la definición de orden multiplicativo de \( a \) módulo \( n \)?
  2. ¿Cuál es \( \operatorname{ord}_5(4) \)?
  3. ¿Qué condición debe cumplir \( a \) para que \( \operatorname{ord}_n(a) \) exista?
  4. Si \( \operatorname{ord}_n(a)=k \) y \( a^m \equiv 1 \pmod{n} \), ¿qué relación debe cumplirse?
  5. ¿Cuál es \( \operatorname{ord}_{10}(3) \)?
  6. Calcula \( \operatorname{ord}_9(2) \).
  7. Si \( \operatorname{ord}_{13}(a)=6 \), ¿cuál es \( \operatorname{ord}_{13}(a^2) \)?
  8. ¿Cómo se relaciona \( \operatorname{ord}_n(a^{-1}) \) con \( \operatorname{ord}_n(a) \), si \( a \) es invertible módulo \( n \)?
  9. Se afirma que \( \operatorname{ord}_7(a)=\operatorname{ord}_7(a^2) \) para todo \( a \) invertible. ¿Qué valor de \( a \) refuta la afirmación?
  10. Calcula \( \operatorname{ord}_{15}(2) \) paso a paso.

Después de esto

Referencias

  • David M. Burton, Elementary Number Theory, 7th edition, McGraw-Hill, 2011. cap. 8
  • Ivan Niven, Herbert S. Zuckerman, Hugh L. Montgomery, An Introduction to the Theory of Numbers, 5th edition, Wiley, 1991. cap. 2