Theoreme d'Euler (nombres)

Théorème d'Euler (nombres)

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 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²²², c'est-à-dire trouver à quoi est congru 7²²² 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.

Ce document provient de « Th%C3%A9or%C3%A8me d%27Euler (nombres) ».