Théorème d'Euler (arithmétique)

Leonhard Euler (1753)

En mathématiques, le théorème d'Euler ou d'Euler-Fermat en arithmétique modulaire, publié en 1761 par le mathématicien suisse Leonhard Euler, s'énonce ainsi :

Pour tout entier n > 0 et tout entier a premier avec n (autrement dit : inversible mod n),

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

où φ est la fonction indicatrice d'Euler et mod désigne la congruence sur les entiers.

Ce théorème est une généralisation du petit théorème de Fermat qui, lui, ne traite que le cas où n est un nombre premier.

Il se démontre en remarquant que l'exposant λ(n) (appelé l'indicatrice de Carmichael de n) du groupe (ℤ/nℤ)^× des inversibles de l'anneau ℤ/nℤ est un diviseur de l'ordre φ(n) de ce groupe (cette propriété, commune à tous les groupes finis, se déduit du théorème de Lagrange sur les groupes).

Il permet la réduction modulo n de puissances. Par exemple, si l'on veut trouver le chiffre des unités de 7²²², c'est-à-dire trouver à quel nombre entre 0 et 9 est congru 7²²² modulo 10, il suffit de voir que 7 et 10 sont premiers entre eux, et que φ(10) = 4. Le théorème d'Euler nous indique donc que $7^{4}\equiv 1{\pmod {10}}.$ On en déduit que $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}}.$ Le chiffre recherché est donc 9.

Autre démonstration

Il existe de nombreuses démonstrations de ce théorème. On a déjà fourni ci-dessus celle qui généralise la preuve du petit théorème de Fermat par le théorème de Lagrange. On peut de même généraliser la démonstration arithmétique élémentaire :

Soient n > 0 et a un entier premier avec n. Notons ${\overline {a}}$ la classe modulo $n$ d'un entier $a$, en particulier ${\overline {a}}\in \left(\mathbb {Z} /n\mathbb {Z} \right)^{\times }$ (où $\left(\mathbb {Z} /n\mathbb {Z} \right)^{\times }$ désigne le groupe des éléments inversibles modulo n).

La bijection $\left(\mathbb {Z} /n\mathbb {Z} \right)^{\times }\to \left(\mathbb {Z} /n\mathbb {Z} \right)^{\times },\;x\mapsto {\overline {a}}x$ permet de réécrire le produit $P:=\prod _{x\in \left(\mathbb {Z} /n\mathbb {Z} \right)^{\times }}x$ :

$P\;=\prod _{x\in \left(\mathbb {Z} /n\mathbb {Z} \right)^{\times }}\left({\overline {a}}x\right)=\;{\overline {a}}^{\operatorname {Card} \left(\left(\mathbb {Z} /n\mathbb {Z} \right)^{\times }\right)}P\;={\overline {a}}^{\varphi (n)}P$.

On conclut en simplifiant par l'inversible $P$ :

${\overline {1}}={\overline {a}}^{\varphi (n)}={\overline {a^{\varphi (n)}}}$.

Voir aussi

• Ordre multiplicatif
• Liste de sujets portant le nom de Leonhard Euler