${\mathbb{Z}}/n{\mathbb{Z}}$

On se fixe un entier $n>1$ et on considère les entiers de 0 à $n-1$ qui forment l'ensemble des restes de division euclidienne d'entiers par l'entier $n$. Cet ensemble est noté ${\mathbb{Z}}/n{\mathbb{Z}}$. Sur cet ensemble on définit les opérations $+$ et $*$ en effectuant les opérations $+$, $-$, $*$ habituelles puis en prenant le reste de la division euclidienne du résultat par $n$.

Par exemple prenons $n=5$: ${\mathbb{Z}}/n{\mathbb{Z}}=\{ 0, 1, 2, 3, 4 \}$. La somme de 2 et 4 est 6, on divise par 5, reste 1, on dit que $2+4=1 \pmod 5$.

Ces opérations possèdent la plupart des propriétés des opérations sur les nombres entiers (commutativité, associativité, distributivité, ...) et la soustraction est l'opération inverse de l'addition. De plus on peut définir l'inverse $u$ d'un élément $a$ de ${\mathbb{Z}}/n{\mathbb{Z}}$ si $a$ est premier avec $n$: en effet, il s'agit de résoudre $a u = 1 \pmod n$. Or cela signifie que le reste de la division de $au$ par $n$ est 1, si on note $q$ le quotient de $au$ par $n$, on a alors:

$$au=qn+1$$

qu'on peut mettre sous la forme de l'équation de Bézout:

$$a u + n \times (- q) =1$$

qui admet une solution si le PGCD de $a$ et $n$ est 1.
Programmer le calcul de l'inverse d'un entier dans ${\mathbb{Z}}/n{\mathbb{Z}}$.

On peut aussi calculer la puissance $k$-ième $a^k \pmod n$ d'un élément de ${\mathbb{Z}}/n{\mathbb{Z}}$. Il existe un algorithme rapide pour calculer cette puissance, basé sur l'idée suivante:
Si $k=0$ on renvoie 1, si $k=1$ on renvoie $a$. Sinon, soit $k$ est pair, dans ce cas $a^k=(a^{k/2})^2 \pmod n$, on appelle récursivement la fonction puissance pour calculer $a^{k/2} \pmod n$, on le multiplie par lui-même et on le réduit modulo $n$ ; soit $k$ est impair, dans ce cas $a^k=(a^{(k-1)/2})^2*a \pmod n$ etc.
Programmer cet algorithme.
Notez que si $n$ est premier, tous les nombres inférieurs à $n$ sont premiers avec $n$ et donc inversibles dans ${\mathbb{Z}}/n{\mathbb{Z}}$ sauf bien sur 0. Les propriétés de ${\mathbb{Z}}/n{\mathbb{Z}}$ sont alors très semblables à celles des nombres réels ou complexes: tout élément sauf 0 est inversibles.

Petit théorème de Fermat: si $n$ est un nombre premier $a^n=a \pmod n$. Ce théorème peut se démontrer par récurrence sur $a$ (c'est vrai pour $a=1$ puis on passe de $a$ à $a+1$ en développant $(a+1)^n$ avec la formule du binôme de Newton, on montre ensuite que tous les $C^k_n$ sont divisibles par $n$ sauf pour $k=0$ et $k=n$ en utilisant le fait que $n$ est premier).
Tester ce résultat en utilisant le programme de puissance rapide ci-dessus.
Lorsque $n$ n'est pas premier, en général $a^n \neq a \pmod n$. Mais il existe une généralisation qui fait intervenir l'indicatrice d'Euler de $n$:
On appelle indicatrice d'Euler $\varphi (n)$ de $n$ le nombre d'entiers compris entre 1 et $n$ qui sont premiers avec $n$.
Par exemple, si $n$ est premier $\varphi (n)=n-1$.
Autre exemple: calculons $\varphi (15)$. Les entiers inférieurs à 15 qui sont premiers avec 15 sont: 1, 2, 4, 7, 8, 11, 13, 14, il y en a 8 donc $\varphi (15)=8$.
Théorème: si $a$ est premier avec $n$ alors $a^\varphi (n)=1 \pmod n$.
Ce théorème est une généralisation du précédent car si $n$ est un nombre premier, $a^\varphi (n)=a^{n-1} \pmod n$ donc $a^n=a^{n-1} \times a=1 \times a=a \pmod n$.
Tester ce résultat.
On verra plus loin (section ) que ce théorème est à l'origine de la méthode de cryptage RSA.