Congruencias · Definición

Teorema de Euler

teoría de números elementalcongruencias

Antes de empezar necesitas conocer

Muchos cálculos con potencias modulares se simplifican al reducir el exponente módulo \(\varphi(n)\). El teorema de Euler es la herramienta que justifica esa reducción cuando el módulo no es primo.

Definición

El teorema de Euler afirma que si \(a\) y \(n\) son coprimos, entonces \(a^{\varphi(n)} \equiv 1 \pmod{n}\), generalizando el pequeño teorema de Fermat a módulos compuestos.

\[a^{\varphi(n)} \equiv 1 \pmod{n}, \quad \gcd(a,n)=1\]

Si \(\gcd(a,n)=1\), al multiplicar cada residuo de un sistema reducido \(r_1,\dots,r_{\varphi(n)}\) por \(a\), se obtiene de nuevo un sistema reducido, así que \(a^{\varphi(n)}\,r_1\cdots r_{\varphi(n)}\equiv r_1\cdots r_{\varphi(n)} \pmod{n}\). Como ese producto es coprimo con \(n\), se puede cancelar y resulta \(a^{\varphi(n)}\equiv 1 \pmod{n}\). Cuando \(n\) es primo, \(\varphi(n)=n-1\) y el resultado se reduce al pequeño teorema de Fermat.

Por ejemplo, para calcular \(7^{222} \bmod 10\): como \(\gcd(7,10)=1\) y \(\varphi(10)=4\), se tiene \(7^{4}\equiv 1 \pmod{10}\). Como \(222=4\cdot 55+2\), resulta \(7^{222}\equiv 7^{2}=49\equiv 9 \pmod{10}\).

Un error típico es aplicar el teorema sin verificar que \(\gcd(a,n)=1\), por ejemplo usando \(2^{\varphi(8)}\equiv 1 \pmod 8\) cuando \(2^4=16\equiv 0\pmod 8\). Otro error frecuente es usar \(n-1\) en lugar de \(\varphi(n)\) como exponente para módulos compuestos.

Para pensar

¿Por qué el teorema de Euler exige que \(\gcd(a,n)=1\)?

Porque \(a\) debe ser invertible módulo \(n\) para poder cancelar el producto de los residuos; sin coprimalidad la cancelación falla.

Ejercicios 10

  1. Enuncia el teorema de Euler con sus hipótesis.
  2. Calcula \(\varphi(12)\).
  3. Calcula el residuo de \(3^{100}\) módulo \(7\) usando el teorema de Euler.
  4. Indica cuál es el valor de \(\varphi(9)\).
  5. Según el teorema de Euler, ¿qué exponente de \(5\) módulo \(8\) produce residuo 1?
  6. Calcula \(11^{203} \bmod 12\).
  7. Usa el teorema de Euler para hallar \(2^{1000} \bmod 9\).
  8. Calcula el último dígito de \(3^{2026}\) en base 10.
  9. Calcula \(5^{2025}\bmod 16\).
  10. Demuestra que \(a^{13}\equiv a\pmod{30}\) para todo \(a\) coprimo con 30, y comprueba con \(a=7\).

Referencias

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