Précision sur le théorème de Fermat-Euler

Par Mathous

Rappel Théorème Fermat-Euler

Rappelons ce théorème :

Théorème Fermat-Euler :

Soit nn un entier supérieur à 11, et ϕ(n)ϕ(n) (indicatrice d'Euler) le nombre d'entiers inférieurs à nn et premiers avec nn.

Pour tout entiera premier avec nn, on a aφ(n)1[n]a^{\varphi (n)} \equiv 1 [n].

Il en résulte que pour tout entier aa premier avec nn, on a aλφ(n)+1a[n]a^{\lambda \varphi(n)+1} \equiv a [n].

Ce théorème est utilisé en cryptographie, notamment pour le codage RSA.
Mais il impose que aa soit premier avec nn.

Qu'en est-il dans le cas contraire ?

Soit nn un entier (supérieur à 11), "quadratfrei"(c'est-à-dire sans facteur carré), et soit mm un entier tel que pour tout diviseur pp premier de nn on ait p1m1p - 1|m - 1.

Soit pp un diviseur premier de nn, et aa un entier quelconque.

  • ou bien aa est premier avec nn, auquel cas ap11[p]a^{p-1}\equiv 1 [p] (petit théorème de Fermat).

Donc am11[p]a^{m-1} \equiv 1 [p] puisque p1m1p - 1|m - 1.

Ceci étant vrai pour tout diviseur pp premier de nn, et nn n'ayant pas de diviseur carré, am11[n]a^{m-1} \equiv 1 [n].

Il en résulte de am11[p]a^{m-1} \equiv 1 [p] que ama[p]a^m \equiv a [p].

  • ou bien aa n'est pas premier avec pp, c'est donc un multiple de pp et a0[p]a \equiv 0 [p] .

Donc ap10[p]a^{p-1} \equiv 0 [p].

D'où am10[p]a^{m-1} \equiv 0 [p] puisque p1m1p - 1|m - 1.

Il en résulte que am0[p]a^m \equiv 0 [p], et donc ama[p]a^m \equiv a [p].

Dans tous les cas (aa premier ou non avec pp), ama[p]a^m \equiv a [p] .

Or, ceci est vrai pour tout diviseur premier pp de nn.

Autrement dit, amaa^{m- a} est un multiple de pp pour tout diviseur premier pp de nn.

Mais nn étant sans facteur carré, il en résulte donc que amaa^{m -a} est un multiple de nn : autrement dit, ama[n]a^m \equiv a [n].

En résumé :

Théorème :

Soit nn un entier (supérieur à 11), quadratfrei, et mm un entier tel que pour tout diviseur pp premier de nn on ait p1m1p- 1|m - 1.

Alors, pour tout entier aa, on a ama[n]a^m \equiv a [n].
On peut préciser que si de plus aa est premier avec nn, on a am11[n]a^{m-1} \equiv 1 [n].

Exemple:

n=33=3×11n = 33 = 3 \times 11
nn est donc sans carré.
On a φ(n)=(31)×(111)=20\varphi (n) = (3 - 1) \times (11 - 1) = 20.

Si on choisit m1=φ(n)=20m - 1 = \varphi(n) = 20 et donc m=21m = 21, on est donc dans la situation du théorème.

Soit a=5a = 5 : il est premier avec nn, et on vérifie bien que am1=5201[n]a^{m-1} = 5^{20} \equiv 1 [n], ainsi que am=5215[n]a^m = 5^{21} \equiv 5 [n].

Si par contre on choisit a=3a = 3 , il n'est plus premier avec nn, et on constate que am1=32012[n]a^{m-1} = 3^{20} \equiv 12 [n] et non pas à 11.

Par contre, on a bien am=3213[n]a^m = 3^{21} \equiv 3 [n].

Contre-exemple:

Si on choisit cette fois n=12=22×3n = 12 = 22 \times 3, on a φ(n)=6\varphi(n) = 6.

On choisit comme précédemment m1=φ(n)=6m - 1 = \varphi(n) = 6 et donc m=7m = 7.

On a encore, pour tout diviseur premier de nn :
21m12 - 1|m - 1 et 31m13 - 1|m - 1.

Par contre, nn n'est plus quadratfrei.

Soit alors a=2a = 2 : am1=264[n]a^{m-1} = 2^6 \equiv 4 [n], ce à quoi on pouvait s'attendre.

Mais am=278[n]a^m = 2^7 \equiv 8 [n], et non pas à 22.

Toutes nos vidéos sur précision sur le théorème de fermat-euler


Posez vos questions

D'autres interrogations sur ce cours ? Démarrez une discussion et obtenez des réponses à des exercices pratiques.

Accéder au forum