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 ${\displaystyle a^{\varphi (n)}}$ é congruente con ${\displaystyle 1}$ módulo n, onde ${\displaystyle \varphi }$ denota a función totiente de Euler; é dicir

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

O recíproco do teorema de Euler tamén é certo: se a congruencia anterior é certa, entón ${\displaystyle a}$ e ${\displaystyle 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 ${\displaystyle n}$. Por exemplo, considere atopar os valores ${\displaystyle 7^{222}{\pmod {10}}}$. Os enteiros 7 e 10 son coprimos e ${\displaystyle \varphi (10)=4}$. Polo tanto, o teorema de Euler resulta ${\displaystyle 7^{4}\equiv 1{\pmod {10}}}$, e conseguimos

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

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