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 Modelo:Math e Modelo:Math son números enteiros positivos coprimos, entón $a^{\phi (n)}$ é congruente con $1$ módulo Modelo:Math, onde $\phi$ denota a función totiente de Euler; é dicir

$a^{\phi (n)}\equiv 1(\mathrm{mod}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}(\mathrm{mod}10)$. Os enteiros 7 e 10 son coprimos e $\phi (10)=4$. Polo tanto, o teorema de Euler resulta $7^4\equiv 1(\mathrm{mod}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(\mathrm{mod}10)$ .

En xeral, ao reducir unha potencia de $a$ módulo $n$ (onde $a$ e $n$ son coprimos), hai que traballar módulo $\phi (n)$ no expoñente de $a$:

se $x\equiv y(\mathrm{mod}\phi (n))$, entón $a^x\equiv a^y(\mathrm{mod}n)$ .

Probas

1. O teorema de Euler pódese probar utilizando conceptos da teoría de grupos: As clases de residuos módulo Modelo:Mvar que son coprimos con Modelo:Mvar 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 é Modelo:Math. O teorema de Lagrange afirma que a orde de calquera subgrupo dun grupo finito divide a orde de todo o grupo, neste caso Modelo:Math. Se Modelo:Mvar é calquera número coprimo con Modelo:Mvar entón Modelo:Mvar está nunha destas clases de residuos, e as súas potencias Modelo:Math módulo Modelo:Mvar forma un subgrupo do grupo de clases de residuos, con Modelo:Math. O teorema de Lagrange di que Modelo:Mvar debe dividir Modelo:Math, é dicir, hai un enteiro Modelo:Mvar tal que Modelo:Math. Isto implica logo,

$a^{\phi (n)}=a^{kM}=(a^k{)}^M\equiv 1^M=1(\mathrm{mod}n).$

2. Tamén hai unha demostración directa: Sexa Modelo:Math un sistema reducido de residuos (Modelo:Math) e sexa Modelo:Mvar calquera enteiro coprimo con Modelo:Mvar. A demostración depende do feito fundamental de que a multiplicación por Modelo:Mvar permuta o Modelo:Mvar: noutras palabras, se Modelo:Math entón Modelo:Math. (Esta lei de cancelación demóstrase no artigo Grupo multiplicativo de números enteiros módulo n.) É dicir, os conxuntos Modelo:Mvar e Modelo:Math, considerados como os conxuntos de clases de congruencia (Modelo:Math), son idénticos (como conxuntos, poden estar listados en diferentes ordes), polo que o produto de todos os números en Modelo:Mvar é congruente (Modelo:Math) co produto de todos os números en Modelo:Mvar :

$\prod _{i=1}^{\phi (n)}{x}_i\equiv \prod _{i=1}^{\phi (n)}a{x}_i=a^{\phi (n)}\prod _{i=1}^{\phi (n)}{x}_i(\mathrm{mod}n),$ e usando a lei de cancelación para cancelar cada Modelo:Mvar dá o teorema de Euler:

$a^{\phi (n)}\equiv 1(\mathrm{mod}n).$

Véxase tamén

Bibliografía

• Modelo:Cita libro
• Modelo:Cita libro
• Modelo:Cita libro
• Modelo:Cita libro
• Modelo:Cita libro

Outros artigos

• Número de Carmichael

Ligazóns externas

• Modelo:Mathworld
• Euler-Fermat Theorem at PlanetMath

Modelo:Control de autoridades