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

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^[1].

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

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

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

Démonstration

Le groupe (ℤ/ $n$ ℤ)^× des inversibles de l'anneau ℤ/ $n$ ℤ est constitué des classes (modulo $n$ ) d'entiers inversibles modulo $n$ , c'est-à-dire premiers avec $n$ . Par conséquent, (ℤ/ $n$ ℤ)^× est d'ordre $φ (n)$ et contient la classe $a$ de $a$ .

On en déduit que $a$ possède un ordre dans (ℤ/ $n$ ℤ)^× et — d'après le théorème de Lagrange — que cet ordre, noté $m$ , divise $φ (n)$ , c'est-à-dire qu'il existe un entier $k$ tel que $φ (n) = mk$ .

Ainsi, comme $a m = 1$ (par définition de $m$ ), on a ${\overline {a}}^{\varphi (n)}={\overline {a}}^{mk}=({\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 CarmichaelFonction de Carmichael ou par le théorème de Lagrange sur les groupes (comme on peut le voir dans la démonstration ci-dessus).

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 à 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.

Note

↑ Présenté à l'Académie de Berlin le 13 février 1755, puis publié par l'Académie des sciences de Saint-Pétersbourg sous le titre « Theoremata circa residua ex divisione potestatum relicta », dans Novi Comment. acad. sc. Petrop., vol. 7, 1761, p. 49-82. L'original en latin est disponible en ligne sur le site du Dartmouth College sous le numéro E262. Traduction en anglais : « math/0608467 », texte en accès libre, sur arXiv.

Article connexe

Ordre multiplicatif

Arithmétique et théorie des nombres

[1] Présenté à l'Académie de Berlin le 13 février 1755, puis publié par l'Académie des sciences de Saint-Pétersbourg sous le titre « Theoremata circa residua ex divisione potestatum relicta », dans Novi Comment. acad. sc. Petrop., vol. 7, 1761, p. 49-82. L'original en latin est disponible en ligne sur le site du Dartmouth College sous le numéro E262. Traduction en anglais : « math/0608467 », texte en accès libre, sur arXiv.

[1]