Théorème d'Euler (nombres)

Un article de Wikipédia, l'encyclopédie libre.

En mathématiques, et plus particulièrement en arithmétique modulaire, le théorème d'Euler est un théorème, nommé ainsi en l'honneur du mathématicien suisse Leonhard Euler, qui stipule que

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

$a^{\varphi(n)} \equiv 1 \mod 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 \mod 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 $7222$ , c'est-à-dire trouver à quoi est congru $7222$ 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