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 e son números enteiros positivos coprimos, entón é congruente con módulo , onde denota a función totiente de Euler; é dicir
O recíproco do teorema de Euler tamén é certo: se a congruencia anterior é certa, entón e 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 . Por exemplo, considere atopar os valores . Os enteiros 7 e 10 son coprimos e . Polo tanto, o teorema de Euler resulta , e conseguimos .
En xeral, ao reducir unha potencia de módulo (onde e son coprimos), hai que traballar módulo no expoñente de :
se , entón .
Probas 1. O teorema de Euler pódese probar utilizando conceptos da teoría de gruposIreland & Rosen, corr. 1 to prop 3.3.2: As clases de residuos módulo que son coprimos con 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 é . O teorema de Lagrange afirma que a orde de calquera subgrupo dun grupo finito divide a orde de todo o grupo, neste caso . Se é calquera número coprimo con entón está nunha destas clases de residuos, e as súas potencias módulo forma un subgrupo do grupo de clases de residuos, con . O teorema de Lagrange di que debe dividir , é dicir, hai un enteiro tal que . Isto implica logo,
2. Tamén hai unha demostración directa:Hardy & Wright, thm. 72Landau, thm. 75 Sexa un sistema reducido de residuos () e sexa calquera enteiro coprimo con . A demostración depende do feito fundamental de que a multiplicación por permuta o : noutras palabras, se entón . (Esta lei de cancelación demóstrase no artigo Grupo multiplicativo de números enteiros módulo n.) É dicir, os conxuntos e , considerados como os conxuntos de clases de congruencia (), son idénticos (como conxuntos, poden estar listados en diferentes ordes), polo que o produto de todos os números en é congruente () co produto de todos os números en :
e usando a lei de cancelación para cancelar cada dá o teorema de Euler:
Notas
Véxase tamén Bibliografía
Outros artigos Número de Carmichael Ligazóns externas
Euler-Fermat Theorem at PlanetMath
Categoría:Teoría de números Categoría:Teoremas