Arithmétique modulaire

Septembre 2026

Congruences

Une congruence signifie que deux nombres donnent le même reste lorsqu'on les divise par un même entier.

1. L'idée

Par exemple :

$17\equiv5\ (mod\ 12)$

Pourquoi ?

$17=12\times1 + 5$

Et :

$5=12\times0 + 5$

Les deux nombres ont donc le même reste : 5.

On peut aussi dire :

$17-5=12$

et 12 est un multiple de 12.

2. Définition mathématique

On écrit :

$a\equiv b\ (mod\ n)\quad où\quad n \in \mathbb{N}\quad et\quad \ a,\ b\ \in \mathbb{Z}$

Si et seulement si :

$n\ |\ (a - b)$

Autrement dit, (a - b) est divisible par n.

Dans notre exemple :

$17 - 5 = 12$

Et :

$12\ |\ 12$

donc

$\fbox{$17\equiv5\ (mod\ 12)$}$

Autre exemple :

$38\equiv8\ (mod\ 10)$

car :

$38=3\times10 + 8$

Et :

$8=0\times10 + 8$

Donc les deux nombres ont le même reste (8) modulo 10.

Mais on peut également écrire :

$38 - 8 = 30$

et 30 est divisible par 10.

Donc :

$\fbox{$38\equiv8\ (mod\ 10)$}$

L'arithmétique modulaire permet de travailler avec des nombres tout en les ramenant dans un ensemble fini de valeurs. Elles constitue une base importante de nombreux calculs en cryptographie.

Dans les courbes elliptiques, par exemple, les coordonnées de points sont calculées modulo un nombre premier p. Les congruences deviennent alors indispensables pour comprendre les opérations effectuées sur la courbe.

Retour au menu quantum