Teorema de Euler

En teoría de números, o teorema de Euler (tamén coñecido como teorema de Fermat-Euler ou teorema totiente de Euler ) afirma que, se n e a son números enteiros positivos coprimos, entón $a^{\varphi (n)}$ é congruente con $1$ módulo n, onde $\varphi$ denota a función totiente de Euler; é dicir

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

O recíproco do teorema de Euler tamén é certo: se a congruencia anterior é certa, entón $a$ e $n$ deben ser coprimos.

O teorema está máis xeneralizado por algúns dos teoremas de Carmichael.

O teorema pódese usar para reducir facilmente grandes potencias módulo $n$. Por exemplo, considere atopar os valores $7^{222}{\pmod {10}}$. Os enteiros 7 e 10 son coprimos e $\varphi (10)=4$. Polo tanto, o teorema de Euler resulta $7^{4}\equiv 1{\pmod {10}}$, e conseguimos

$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 xeral, ao reducir unha potencia de $a$ módulo $n$ (onde $a$ e $n$ son coprimos), hai que traballar módulo $\varphi (n)$ no expoñente de $a$:

se $x\equiv y{\pmod {\varphi (n)}}$, entón $a^{x}\equiv a^{y}{\pmod {n}}$ .

Probas

1. O teorema de Euler pódese probar utilizando conceptos da teoría de grupos: As clases de residuos módulo n que son coprimos con n forman un grupo baixo a multiplicación (ver o artigo Grupo multiplicativo de enteiros módulo n para máis detalles). A orde dese grupo é φ(n). O teorema de Lagrange afirma que a orde de calquera subgrupo dun grupo finito divide a orde de todo o grupo, neste caso φ(n). Se a é calquera número coprimo con n entón a está nunha destas clases de residuos, e as súas potencias a, a², ..., a^k módulo n forma un subgrupo do grupo de clases de residuos, con a^k ≡ 1 (mod n). O teorema de Lagrange di que k debe dividir φ(n), é dicir, hai un enteiro M tal que kM = φ(n). Isto implica logo,

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

2. Tamén hai unha demostración directa: Sexa R = {x₁, x₂, ..., x_φ(n)} un sistema reducido de residuos (mod n) e sexa a calquera enteiro coprimo con n. A demostración depende do feito fundamental de que a multiplicación por a permuta o x_i: noutras palabras, se ax_j ≡ ax_k (mod n) entón j = k. (Esta lei de cancelación demóstrase no artigo Grupo multiplicativo de números enteiros módulo n.) É dicir, os conxuntos R e aR = {ax₁, ax₂, ..., ax_φ(n)}, considerados como os conxuntos de clases de congruencia (mod n), son idénticos (como conxuntos, poden estar listados en diferentes ordes), polo que o produto de todos os números en R é congruente (mod n) co produto de todos os números en aR :

$\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}},$ e usando a lei de cancelación para cancelar cada x_i dá o teorema de Euler:

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

Véxase tamén

Bibliografía

• Gauss, Carl Friedrich; Clarke, Arthur A. (translated into English) (1986). Disquisitiones Arithemeticae (Second, corrected edition). New York: Springer. ISBN 0-387-96254-9. 
• Gauss, Carl Friedrich; Maser, H. (translated into German) (1965). Untersuchungen uber hohere Arithmetik (Disquisitiones Arithemeticae & other papers on number theory) (Second edition). New York: Chelsea. ISBN 0-8284-0191-8. 
• Hardy, G. H.; Wright, E. M. (1980). An Introduction to the Theory of Numbers (Fifth edition). Oxford: Oxford University Press. ISBN 978-0-19-853171-5. 
• Ireland, Kenneth; Rosen, Michael (1990). A Classical Introduction to Modern Number Theory (Second edition). New York: Springer. ISBN 0-387-97329-X. 
• Landau, Edmund (1966). Elementary Number Theory. New York: Chelsea. 

Outros artigos

• Número de Carmichael

Ligazóns externas

• Weisstein, Eric W. "Euler's Totient Theorem". MathWorld. 
• Euler-Fermat Theorem at PlanetMath