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:

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

On termine la démonstration en utilisant le théorème suivant:

\forall x \in \mathbb{N}, x\times 1 = x.

Advertisements
Cet article, publié dans Arithmétique, est tagué , , , , . Ajoutez ce permalien à vos favoris.

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

  1. Anonyme dit :

    Super clair !

  2. Anonyme dit :

    Très clair et avec une pointe d’humour en prime.
    Merci !

  3. Anonyme dit :

    Merci beaucoup. Pour moi qui ne suis encore qu’en SUP, c’est très agréable de pouvoir démontrer ce théorème et ce sera très intéressant d’en avoir une approche différente l’année prochaine. 🙂

  4. ATIF dit :

    MERCI POUR LA BONNE ET CLAIRE DÉMONSTRATION

  5. Ping : Le théorème de Wilson | Blogdemaths

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s