2.1 Arithmétique modulaire

L'arithmétique modulaire est un outil découvert par Gauss en 1801. Le concept en est très simple. Imaginons que la suite infinie de nombres réels ne soit pas infinie mais qu'elle revienne à 0 après un nombre $N$. On peut visualiser un système modulaire comme une horloge: après un certain nombre, on revient au point de départ. Une horloge à 12 chiffres serait un système modulaire à base 12. Il faut cependant considérer le chiffre 12 comme 0.

L'arithmétique modulaire permet de faire des calculs sur des cycles. Par exemple, pour reprendre l'exemple de l'horloge, si on ajoute 7 au nombre 10, on n'obtient pas 17, mais 5. Dans ce cas, on dit que 17 et 5 sont congrus modulo 12. Deux nombres sont congrus modulo $N$ si et seulement si

$$N\vert(a-b)$$

c'est-à-dire si la différence entre $a$ et $b$ est un multiple de $N$. Habituellement, puisque l'arithmétique modulaire est très souvent utilisée pour des cas concrets, $a$, $b$ et $N$ sont des nombres entiers positifs. Nous pouvons écrire le cas de congruence

$$a=b\, \, \, (\bmod N)$$

L'ensemble des nombres congrus modulo $N$ à $a$ se note $[a]_{N}$. Si $b\in [a]_{N}$, par définition $N\vert(a-b)$. On peut aussi dire que $a$ et $b$ on le même reste de la division entière par $N$. C'est cette dernière représentation qui nous sera le plus utile. Par exemple, pour trouver la solution de

$$x=120\, \, \, (\bmod 26)$$

il suffit de soustraire 26 à 120 répétitivement jusqu'à ce qu'on obtienne un nombre plus petit que 26. Ce nombre est la réponse. Dans ce cas, $x=16$.

L'ensemble modulo $N$ $\{0,...,N-1\}$ est muni seulement de deux opérations, la multiplication et l'addition. Cela comprend évidemment leurs inverses, la division et la soustraction. Leur fonctionnement est exactement comme celui usuel, excepté que le résultat est réduit modulo $N$.