Teorema de Euler

Teorema de exponenciación modular

En teoría de números , el teorema de Euler (también conocido como teorema de Fermat-Euler o teorema totiente de Euler ) establece que, si n y a son números enteros positivos coprimos , entonces es congruente con módulo n , donde denota la función totiente de Euler ; es decir ${\displaystyle a^{\varphi (n)}}$ ${\displaystyle 1}$ ${\displaystyle \varphi }$

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

En 1736, Leonhard Euler publicó una demostración del pequeño teorema de Fermat ^[1] (enunciado por Fermat sin demostración), que es la restricción del teorema de Euler al caso en que n es un número primo. Posteriormente, Euler presentó otras demostraciones del teorema, que culminaron con su artículo de 1763, en el que demostró una generalización al caso en que n no es primo. ^[2]

El inverso del teorema de Euler también es cierto: si la congruencia anterior es verdadera, entonces y deben ser coprimos. ${\displaystyle a}$ ${\displaystyle n}$

El teorema se generaliza aún más mediante algunos de los teoremas de Carmichael .

El teorema se puede utilizar para reducir fácilmente grandes potencias módulo . Por ejemplo, considere encontrar el dígito decimal de las unidades de , es decir . Los números enteros 7 y 10 son coprimos y . Por lo tanto, el teorema de Euler da , 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 coprimos), 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 utiliza ampliamente en las comunicaciones por Internet . En este criptosistema, se utiliza el teorema de Euler siendo n el producto de dos números primos grandes y la seguridad del sistema se basa en la dificultad de factorizar un número entero de este tipo.

Pruebas

1. El teorema de Euler se puede demostrar usando conceptos de la teoría de grupos : ^[3] Las clases de residuos módulo n que son coprimos con n forman un grupo bajo multiplicación (ver el artículo Grupo multiplicativo de números enteros módulo n para más 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 a es cualquier número coprimo con n entonces a está en una de estas clases de residuos, y sus potencias a , a ² , ... , a ^k módulo n forman un subgrupo del grupo de clases de residuos, con a ^k ≡ 1 (mod n ) . El teorema de Lagrange dice que k debe dividir a φ ( 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{\pmod {n}}.}$

2. También hay una prueba directa: ^{[4] [5]} Sea R = { x ₁ , x ₂ , ... , x _{φ ( n )} } un sistema de residuos reducidos ( mod n ) y sea a cualquier entero coprimo con n . La prueba 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 números enteros módulo n . ^[6] ) Es decir, los conjuntos R y aR = { ax ₁ , ax ₂ , ... , ax _{φ ( n )} } , considerados como conjuntos de clases de congruencia ( mod n ), son idénticos (como conjuntos, pueden estar enumerados 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 usando la ley de cancelación para cancelar cada x _i se obtiene el teorema de Euler:

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

Véase también

• Número de Carmichael
• Criterio de Euler
• Teorema de Wilson

Notas

1. Ver:
   • Leonhard Euler (presentado: 2 de agosto de 1736; publicado: 1741) "Theorematum quorundam ad numeros primos spectantium demonstratio" (Una prueba de ciertos teoremas sobre números primos), Commentarii academiae scientiarum Petropolitanae , 8  : 141-146.
   • Para más detalles sobre este artículo, incluida una traducción al inglés, consulte: The Euler Archive.
2. Ver:
   • L. Euler (publicado: 1763) "Theoremata arithmetica nova methodo demonstrata" (Prueba de un nuevo método en la teoría de la aritmética), Novi Commentarii academiae scientiarum Petropolitanae , 8  : 74–104. El teorema de Euler aparece como "Teorema 11" en la página 102. Este artículo fue presentado por primera vez en la Academia de Berlín el 8 de junio de 1758 y en la Academia de San Petersburgo el 15 de octubre de 1759. En este artículo, la función totiente de Euler, , no se nombra sino que se hace referencia a ella como "numerus partium ad N primarum" (el número de partes primas de N ; es decir, el número de números naturales que son menores que N y primos entre sí de N ). ${\displaystyle \varphi (n)}$
   • Para más detalles sobre este artículo, véase: El Archivo Euler.
   • Para una revisión del trabajo de Euler a lo largo de los años que condujeron al teorema de Euler, consulte: Ed Sandifer (2005) "La prueba de Euler del pequeño teorema de Fermat" Archivado el 28 de agosto de 2006 en Wayback Machine.
3. Ireland & Rosen, corrección 1 a la propuesta 3.3.2
4. Hardy y Wright, tm. 72
5. Landau, obra 75
6. Véase el lema de Bézout

Referencias

Las Disquisitiones Arithmeticae han sido traducidas del latín ciceroniano de Gauss al inglés y al alemán. La edición alemana incluye todos sus artículos 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 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 números (quinta edición) , Oxford: Oxford University Press , ISBN 978-0-19-853171-5
• Irlanda, Kenneth; Rosen, Michael (1990), Una introducción clásica a la teoría de números moderna (segunda edición) , Nueva York: Springer , ISBN 0-387-97329-X
• Landau, Edmund (1966), Teoría elemental de números , Nueva York: Chelsea

Enlaces externos

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