Théorème d'Euler (nombres)

Pour les articles homonymes, voir Théorème d'Euler.

En mathématiques, le théorème d'Euler en arithmétique modulaire a été publié en 1761 par le mathématicien suisse Leonhard Euler.

Théorème d'Euler —  Soit $n$ un entier naturel et $a$ un entier premier avec $n$, alors

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

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

Démonstration

Comme $(\mathbb{Z}/n\mathbb{Z})^*$, l'ensemble des éléments inversibles de $(\mathbb{Z}/n\mathbb{Z},\times)$, est l'ensemble des générateurs de $(\mathbb{Z}/n\mathbb{Z},+)$, il a pour ordre $\varphi(n)$. Pour plus de détails voir l'article Anneau Z/nZ.

Soit $a$ un entier premier avec $n$, la classe $\overline{a}$ de $a$ dans $\mathbb{Z}/n\mathbb{Z}$ est alors génératrice de $\mathbb{Z}/n\mathbb{Z}$, donc appartient à $(\mathbb{Z}/n\mathbb{Z})^*$. On en déduit que l'ordre de $\overline{a}$ (noté $m$) dans $(\mathbb{Z}/n\mathbb{Z})^*$ divise $\varphi(n)$ d'après le théorème de Lagrange, d'où l'existence d'un entier $k$ tel que $\varphi(n)= k\times m$.

Ainsi comme $\overline{a}^{m}=\overline{1}$ (par définition de m), on a

$\overline{a}^{\varphi(n)}=\overline{a}^{k\times m}=(\overline{a}^{m})^{k}=\overline{1}^{k}=\overline{1};$

ce qui s'écrit également,

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

Ce théorème est une généralisation du petit théorème de Fermat (qui ne traite que le cas où $n$ est un nombre premier), et est lui-même généralisé par le théorème de Carmichaël.

Ce théorème permet simplement la réduction modulo $n$ de puissance. Par exemple, si on veut trouver le chiffre des unités de $7^{222}$, c'est-à-dire trouver à quoi est congru $7^{222}$ modulo $10$, il suffit de voir que $7$ et $10$ sont premiers entre eux, et que $\varphi(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$.