Teorema de Euler

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 enteros positivos coprimos , entonces${\displaystyle a^{\varphi (n)}}$es congruente con${\displaystyle 1}$módulo n , donde${\displaystyle \varphi }$ denota la función totiente de Euler ; es decir

${\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, culminando con su artículo de 1763, en el que demostró una generalización al caso en que n no es primo. ^{[ 2 ]}

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

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

El teorema puede utilizarse para reducir fácilmente grandes potencias módulo${\displaystyle n}$. Por ejemplo, considere encontrar el dígito decimal de las unidades de${\displaystyle 7^{222}}$, es decir${\displaystyle 7^{222}{\pmod {10}}}$. Los números enteros 7 y 10 son coprimos, y${\displaystyle \varphi (10)=4}$. Por lo tanto, el teorema de Euler produce${\displaystyle 7^{4}\equiv 1{\pmod {10}}}$y obtenemos${\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${\displaystyle a}$módulo${\displaystyle n}$(dónde${\displaystyle a}$y${\displaystyle n}$son coprimos), uno necesita trabajar módulo${\displaystyle \varphi (n)}$en el exponente de${\displaystyle a}$:

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

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

1. El teorema de Euler se puede demostrar utilizando conceptos de la teoría de grupos : ^{[ 3 ]} Las clases de residuos módulo n que son coprimas con n forman un grupo bajo la multiplicación (véase el artículo Grupo multiplicativo de 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, existe un entero M tal que kM = φ ( n ) . Esto implica entonces,

${\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 reducido ( mod n ) y sea a cualquier entero coprimo con n . La prueba se basa en el hecho fundamental de que la multiplicación por a permuta el 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 . ^{[ 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 listados 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 utilizando la ley de cancelación para cancelar cada x _i se obtiene el teorema de Euler:

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

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

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 trabajos sobre teoría de números: todas las demostraciones de la 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 über hohere Arithmetik (Disquisitiones Arithemeticae & other papers on number theory) (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  ed.), Oxford: Oxford University Press , ISBN 978-0-19-853171-5
• Ireland, Kenneth; Rosen, Michael (1990), Introducción clásica a la teoría moderna de números (Segunda edición) , Nueva York: Springer , ISBN 0-387-97329-X
• Landau, Edmund (1966), Teoría elemental de números , Nueva York: Chelsea

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