Teorema de Euler - Euler's theorem

En teoría de números , el teorema de Euler (también conocido como el teorema de Fermat-Euler o el teorema del totient de Euler ) establece que si n y a son enteros coprimos positivos, entonces a elevado a la potencia del totiente de n es congruente con uno, módulo n , o:

${\ Displaystyle a ^ {\ varphi (n)} \ equiv 1 {\ pmod {n}}}$

donde está la función totient de Euler . En 1736, Leonhard Euler publicó su prueba del pequeño teorema de Fermat , que Fermat había presentado sin pruebas. Posteriormente, Euler presentó otras demostraciones del teorema, culminando con el "teorema de Euler" en su artículo de 1763, en el que intentó encontrar el exponente más pequeño para el cual el pequeño teorema de Fermat siempre fue cierto. ${\ Displaystyle \ varphi (n)}$

Lo contrario del teorema de Euler también es cierto: si la congruencia anterior es verdadera, entonces y debe ser coprime. ${\ Displaystyle a}$${\ Displaystyle n}$

El teorema es una generalización del pequeño teorema de Fermat , y el teorema de Carmichael lo generaliza más .

El teorema se puede utilizar para reducir fácilmente el módulo de grandes potencias . Por ejemplo, considere encontrar el dígito decimal de las unidades , es decir . Los enteros 7 y 10 son coprimos y . Entonces el teorema de Euler cede y obtenemos . ${\ Displaystyle n}$${\ Displaystyle 7 ^ {222}}$${\ Displaystyle 7 ^ {222} {\ pmod {10}}}$${\ Displaystyle \ varphi (10) = 4}$${\ Displaystyle 7 ^ {4} \ equiv 1 {\ pmod {10}}}$${\ Displaystyle 7 ^ {222} \ equiv 7 ^ {4 \ times 55 + 2} \ equiv (7 ^ {4}) ^ {55} \ times 7 ^ {2} \ equiv 1 ^ {55} \ times 7 ^ {2} \ equiv 49 \ equiv 9 {\ pmod {10}}}$

En general, al reducir una potencia de módulo (donde y son coprime), es necesario trabajar módulo en el exponente de : ${\ Displaystyle a}$${\ Displaystyle n}$${\ Displaystyle a}$${\ Displaystyle n}$${\ Displaystyle \ varphi (n)}$${\ Displaystyle a}$

si , entonces .${\ Displaystyle x \ equiv y {\ pmod {\ varphi (n)}}}$${\ Displaystyle a ^ {x} \ equiv a ^ {y} {\ pmod {n}}}$

El teorema de Euler es la base del criptosistema RSA , que se usa ampliamente en las comunicaciones por Internet . En este criptosistema, se utiliza el teorema de Euler siendo n un producto de dos números primos grandes , y la seguridad del sistema se basa en la dificultad de factorizar dicho número entero.

Pruebas

1. Euler es teorema se puede probar usando conceptos de la teoría de los grupos : Las clases de residuos modulo n que son primos entre sí a n forman un grupo bajo la multiplicación (véase el artículo grupo multiplicativo de enteros módulo n para los detalles). El orden de ese grupo es φ ( n ) . El teorema de Lagrange establece que el orden de cualquier subgrupo de un grupo finito divide el orden de todo el grupo, en este caso φ ( n ) . Si una es cualquier número primos entre sí a n entonces una está en una de estas clases de residuos, y sus poderes a , un ² , ..., un ^k módulo n formar un subgrupo del grupo de clases de residuos, con una ^k ≡ 1 ( mod n ) . El teorema de Lagrange dice que k debe dividir φ ( n ) , es decir, hay un entero M tal que kM = φ ( n ) . Esto entonces implica,

${\ Displaystyle a ^ {\ varphi (n)} = a ^ {kM} = (a ^ {k}) ^ {M} \ equiv 1 ^ {M} = 1 \ equiv 1 {\ pmod {n}}. }$

2. También hay una prueba directa: Sea R = { x ₁ , x ₂ , ..., x _{φ ( n )} } un sistema de residuo reducido ( mod n ) y sea a cualquier coprimo entero de n . La demostración depende del hecho fundamental de que la multiplicación por a permuta x _i : en otras palabras, si ax _j ≡ ax _k (mod n ) entonces j = k . (Esta ley de cancelación se demuestra en el artículo Grupo multiplicativo de enteros módulo n .) Es decir, los conjuntos R y aR = { ax ₁ , ax ₂ , ..., ax _{φ ( n )} } , considerados como conjuntos de congruencia clases ( mod n ), son idénticas (como conjuntos; pueden enumerarse en diferentes órdenes), por lo que el producto de todos los números en R es congruente ( mod n ) con el producto de todos los números en aR :

${\ Displaystyle \ prod _ {i = 1} ^ {\ varphi (n)} x_ {i} \ equiv \ prod _ {i = 1} ^ {\ varphi (n)} ax_ {i} = a ^ {\ varphi (n)} \ prod _ {i = 1} ^ {\ varphi (n)} x_ {i} {\ pmod {n}},}$y el uso de la ley de cancelación para cancelar cada x _i da el teorema de Euler:

${\ Displaystyle a ^ {\ varphi (n)} \ equiv 1 {\ pmod {n}}.}$

Ver también

• Función de Carmichael
• Criterio de Euler
• El pequeño teorema de Fermat
• Teorema de wilson

Notas

Referencias

The Disquisitiones Arithmeticae se ha traducido del latín ciceroniano de Gauss al inglés y al alemán. La edición alemana incluye todos sus trabajos sobre teoría de números: todas las pruebas de reciprocidad cuadrática, la determinación del signo de la suma de Gauss, las investigaciones sobre la reciprocidad bicuadrática y notas inéditas.

• Gauss, Carl Friedrich; Clarke, Arthur A. (traducido al inglés) (1986), Disquisitiones Arithemeticae (Segunda edición corregida) , Nueva York: Springer , ISBN 0-387-96254-9
• Gauss, Carl Friedrich; Maser, H. (traducido al alemán) (1965), Untersuchungen uber hohere Arithmetik (Disquisitiones Arithemeticae y otros artículos sobre teoría de números) (Segunda edición) , Nueva York: Chelsea, ISBN 0-8284-0191-8
• Hardy, GH; Wright, EM (1980), Introducción a la teoría de los números (quinta edición) , Oxford: Oxford University Press , ISBN 978-0-19-853171-5
• Irlanda, Kenneth; Rosen, Michael (1990), A Classical Introduction to Modern Number Theory (Segunda edición) , Nueva York: Springer , ISBN 0-387-97329-X
• Landau, Edmund (1966), Teoría de números elemental , Nueva York: Chelsea

enlaces externos

• Weisstein, Eric W. "Teorema de Totient de Euler" . MathWorld .
• Teorema de Euler-Fermat en PlanetMath