Une démonstration arithmétique du théorème d’Euler

La plupart du temps, la démonstration du théorème d’Euler (en arithmétique… car des théorèmes d’Euler, il y en a plein !) fait appel à la notion de groupe et au théorème de Lagrange (ce qui est le cas de la démonstration postée sur la page Wikipédia française).

Je vous propose de voir dans cet article une autre démonstration de ce théorème (même si fondamentalement, l’idée sous-jacente est la même) qui ne repose que sur les propriétés arithmétiques des entiers.

Que dit ce théorème ?

Avant cela, rappelons ce que dit ce théorème d’Euler: si $n$ est un entier naturel non nul alors pour tout entier naturel $a$ premier avec $n$ , on a la congruence:

$a^{\phi(n)} \equiv 1 \mod(n)$

où le nombre $\phi(n)$ est le nombre d’entiers naturels inférieurs à $n$ qui sont premiers avec $n$ .

Ce théorème a trouvé une application très importante dans les années 70: il est à la base du système de cryptographie RSA (largement utilisé de nos jours) où il permet le déchiffrement d’un message codé.

Etude de la demonstration sur un exemple

Prenons $n=10$ et $a=7$ . Commençons par trouver la valeur de $\phi(10)$ . Il s’agit du nombre d’entiers naturels compris entre 1 et 10 qui sont premiers avec 10. Voici l’ensemble de ces entiers:

$U:=\{1; 3; 7; 9 \}$

Ils sont au nombre de 4, donc $\phi(10)=4$ . Ainsi, le théorème d’Euler affirme que $a^4 \equiv 1 \mod (10)$ c’est-à-dire $7^4 \equiv 1 \mod (10)$ . Ce résultat peut bien entendu être vu directement car $7^4= 2401 = 10 \times 240 + 1$ . Cependant, nous allons le démontrer d’une autre façon qui pourra se généraliser.

Tout d’abord, multiplions tous les nombres de l’ensemble $U$ par 7. On obtient l’ensemble noté $7U$ suivant:

$7U = \{7; 21; 49; 63 \}$

Et maintenant examinons chaque membre de cet ensemble modulo 10:

$7 \equiv 7 \mod (10)$
$21 \equiv 1 \mod (10)$
$49 \equiv 9 \mod (10)$
$63 \equiv 3 \mod (10)$

Comme les règles sur le produit des congruences le permettent, on peut multiplier toutes ces congruences membre à membre et on obtient:

$7 \times 21 \times 49 \times 63 \equiv 7 \times 1 \times 9 \times 3 \mod (10)$

En réécrivant cela, on a:

$(7 \times 1) \times (7 \times 3) \times (7 \times 7) \times (7 \times 9) \equiv 1 \times 3 \times 7 \times 9 \mod (10)$

Et donc (c’est à ce moment-là que tout s’éclaire… sauf que cette fois la lumière n’est pas venue de Laurent Blanc) :

$7^4 \times (1 \times 3 \times 7 \times 9) \equiv 1 \times 3 \times 7 \times 9 \mod(10)$

On est content car le $7^4$ est apparu ! Pour conclure, il faudrait pouvoir simplifier ce terme $1 \times 3 \times 7 \times 9$ …

Voyons voir: $1 \times 3 \times 7 \times 9 = 189 \equiv 9 \mod (10)$ . Or quand on mutliplie cette congruence par 9 des deux côtés, on a $189 \times 9 \equiv 9 \times 9 =81 \equiv 1 \mod (10)$ !

Donc pour simplifier le produit $1 \times 3 \times 7 \times 9$ , il suffit de multiplier par 9 des deux côtés, et il restera:

$7^4 \times 189 \times 9 \equiv 189 \times 9 \mod (10)$

donc

$7^4 \equiv 1 \mod (10)$ !

En fait, ce qui a été essentiel dans notre raisonnement, c’est que:

1) les ensembles $U$ et $7U$ sont identiques si on les regarde modulo 10
2) le produit des nombres qui sont premiers avec 10 peut se simplifier

Etendons ces deux idées pour des entiers $n$ et $a$ quelconques.

Cas général

Dans le cas général, voici les deux propriétés que nous allons utiliser:

Prop. 1: Si $a$ est un entier naturel premier avec $n$ , alors il existe un entier naturel $b$ tel que $ab \equiv 1 \mod (n)$

Cette propriété n’est rien d’autre qu’une reformulation du fameux théorème de Bézout !

Prop. 2: Si $a_1$ et $a_2$ sont deux entiers naturels premiers avec $n$ , alors le produit $a_1 a_2$ est aussi premier avec $n$ .

Il s’agit d’un corollaire du théorème de Bézout.

Nous sommes à présents prêts pour démontrer notre bon vieux théorème d’Euler (et c’est le cas de le dire car ce théorème est connu depuis 3 siècles et demi. Ca c’est de la bonne blague où je ne m’y connais pas).

La démonstration:

La démonstration générale suit les mêmes lignes que l’exemple plus haut.

Soit $n$ un entier naturel non nul et $a$ un entier premier avec $n$ . Par définition même de $\phi(n)$ , il y a $\phi(n)$ nombres compris entre 1 et $n$ qui sont premiers avec $n$ . On les note $a_1, a_2, \cdots, a_{\phi(n)}$ . Comme dans notre exemple plus haut, on peut donc former les ensembles $U$ et $aU$ suivants:

$U = \{ a_1, a_2, \cdots, a_{\phi(n)}\}$

$aU =\{ a a_1, a a_2, \cdots , aa_{\phi(n)}\}$

Etape 1: Nous allons commencer par montrer que ces deux ensembles sont égaux modulo $n$ c’est-à-dire que pour tout indice $i$ , il existe un unique indice $j$ tel que $a a_i \equiv a_j \mod (n)$ :

• Existence: Puisque $a$ et $a_i$ sont premiers avec $n$ , leur produit est aussi un nombre premier avec $n$ (prop. 2) dont le reste dans la division euclidienne par $n$ est un nombre encore compris entre 1 et $n$ qui est premier avec $n$ … C’est donc un des $a_j$ !

• Unicité: S’il y a deux indices $i_1$ et $i_2$ tels que $a a_{i_1}$ et $a a_{i_2}$ soient congrus au même entier $a_j$ alors:

$a a_{i_1} \equiv a a_{i_2} \mod (n)$

Et donc si $b$ est un entier tel que décrit dans la proposition 1 (c’est-à-dire $ab \equiv 1 \mod (n)$ ), alors:

$ba a_{i_1} \equiv ba a_{i_2} \mod (n)$

c’est-à-dire $a_{i_1} \equiv a_{i_2} \mod (n)$ … Et comme $a_{i_1}$ et $a_{i_2}$ sont tous les deux compris entre 1 et $n$ et qu’il sont congrus, c’est donc qu’ils sont égaux, d’où $i_1 = i_2$ !

Etape 2: Nous venons donc de montrer que les ensembles $aU$ et $U$ sont égaux modulo $n$ ; ainsi, le produit des éléments de $aU$ est égal au produit des éléments de $U$ modulo $n$ , ce qui s’écrit:

$a a_1 \times a a_2 \times \cdots \times a a_{\phi(n)} \equiv a_1 \times a_2 \times \cdots \times a_{\phi(n)} \mod(n)$

En regroupant tous les $a$ dans le membre de gauche, on obtient:

$a^{\phi(n)} (a_1 \times a_2 \times \cdots \times a_{\phi(n)}) \equiv a_1 \times a_2 \times \cdots \times a_{\phi(n)} \mod(n)$

D’après la propriété 2 le nombre $a_1 \times a_2 \times \cdots \times a_{\phi(n)}$ est premier avec $n$ , donc d’après la propriété 1 il existe un entier $b$ tel que le produit $(a_1 \times a_2 \times \cdots \times a_{\phi(n)}) b$ est congru à 1 modulo $n$ , donc en multipliant l’égalité précédente par ce $b$ , on obtient: