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

Par Mathous

Rappel Théorème Fermat-Euler

Rappelons ce théorème :

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

Qu'en est-il dans le cas contraire ?

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

Soit $p$ un diviseur premier de $n$, et $a$ un entier quelconque.

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

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

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

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

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

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

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

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

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

Or, ceci est vrai pour tout diviseur premier $p$ de $n$.

Autrement dit, $a^{m- a}$ est un multiple de $p$ pour tout diviseur premier $p$ de $n$.

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

En résumé :

Exemple:

$n = 33 = 3 \times 11$
$n$ est donc sans carré.
On a $\varphi (n) = (3 - 1) \times (11 - 1) = 20$.

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

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

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

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

Contre-exemple:

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

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

On a encore, pour tout diviseur premier de $n$ :
$2 - 1|m - 1$ et $3 - 1|m - 1$.

Par contre, $n$ n'est plus quadratfrei.

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

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

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