Par exemple prenons :
.
La somme de 2 et 4 est 6, on divise par 5, reste 1, on dit que
.
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 d'un élément
de
si
est premier avec
: en effet, il s'agit de résoudre
. Or cela signifie que le reste de la division de
par
est 1, si on note
le quotient de
par
, on a alors:
On peut aussi calculer la puissance -ième
d'un élément de
.
Il existe un algorithme rapide pour calculer cette puissance, basé sur
l'idée suivante:
Si on renvoie 1, si
on renvoie
.
Sinon, soit
est pair, dans ce cas
,
on appelle récursivement la fonction puissance pour calculer
, on le multiplie par lui-même et on le réduit
modulo
; soit
est impair, dans ce cas
etc.
Programmer cet algorithme.
Notez que si est premier, tous les nombres inférieurs à
sont premiers avec
et donc inversibles dans
sauf bien
sur 0. Les propriétés de
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 est un nombre premier
.
Ce théorème peut se démontrer par récurrence sur
(c'est vrai pour
puis on passe de
à
en développant
avec la formule du binôme de Newton, on montre ensuite que tous
les
sont divisibles par
sauf pour
et
en utilisant
le fait que
est premier).
Tester ce résultat en utilisant le programme de puissance rapide ci-dessus.
Lorsque n'est pas premier, en général
. Mais
il existe une généralisation qui fait intervenir
l'indicatrice d'Euler de
:
On appelle indicatrice d'Euler
de
le nombre d'entiers
compris entre 1 et
qui sont premiers avec
.
Par exemple, si est premier
.
Autre exemple: calculons
. 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
.
Théorème: si est premier avec
alors
.
Ce théorème est une généralisation du précédent car si
est un nombre premier,
donc
.
Tester ce résultat.
On verra plus loin (section ) que ce théorème
est à l'origine de la méthode de cryptage RSA.