Théorie > Théorie des nombres > Arithmétique modulaire


Général

Introduction Chapitre entier

Points théoriques

Définition Propriétés Exemple d'utilisation Critères de divisibilité Théorème de Wilson

Exercices

Exercice 1 Exercice 2 Exercice 3 Exercice 4 Exercice 5 Exercice 6 Exercice 7

Définition

Notion de modulo

Si $n$ est un naturel non nul et $a, b$ sont des entiers tels que $a-b$ est divisible par $n$, alors on dit que $a$ et $b$ sont égaux modulo $n$, ou que $a$ est congru à $b$ modulo $n$. Deux nombres sont en fait égaux modulo $n$ s'ils possèdent le même reste après division par $n$.
Il existe plusieurs façons équivalentes de noter cela :
$$\begin{align}
a &\equiv b \mod n\\
a &\equiv b \pmod n\\
a &\equiv b \pod n
\end{align}$$ Il arrive même que l'on note simplement $a \equiv b$ lorsque $n$ est fixé pour de bon et ne nécessite pas d'être mentionné.

Remarque : Les nombres $a$ et $b$ peuvent ici être négatifs, on a par exemple $8 \equiv -2 \pmod 5$ puisque $8-(-2)= 10$ est divisible par $5$.

Utilisation

La façon la plus courante d'utiliser les modulos est de se fixer un certain naturel non nul $n$, et de se mettre à travailler "modulo $n$". On se met alors à voir le signe $\equiv$ comme une simple égalité, c'est-à-dire qu'on ne différencie plus deux nombres qui possèdent le même reste après division par $n$ : ils sont égaux modulo $n$. Notons tout de même que cela a bien un sens de le considérer comme une égalité puisque $x \equiv x$ et, si $a \equiv b$ et $b \equiv c$, alors $a \equiv c$.

Par exemple, pour $n = 3$, on a
$$\begin{align}
\dots \equiv -9 \equiv -6 \equiv -3 &\equiv 0 \equiv 3 \equiv 6 \equiv 9 \equiv \dots \\
\dots \equiv -8 \equiv -5 \equiv -2 &\equiv 1 \equiv 4 \equiv 7 \equiv 10 \equiv \dots \\
\dots \equiv -7 \equiv -4 \equiv -1 &\equiv 2 \equiv 5 \equiv 8 \equiv 11 \equiv \dots
\end{align}$$ Ainsi, lorsqu'on travaille modulo $3$, il n'y a en fait plus que $3$ nombres distincts : $0$, $1$ et $2$. Tous les autres nombres entiers sont égaux à l'un de ces trois nombres.

C'est pour cette raison qu'il est parfois utile de se fixer un certain $n$ et de se mettre à travailler modulo $n$. Il est en effet plus simple de n'avoir plus que $n$ nombres à manipuler plutôt qu'une infinité!

Remarque : $n$ peut théoriquement être égal à $1$, mais on ne prend en pratique que des $n$ supérieurs ou égaux à $2$. Cela n'a en fait aucun intérêt de travailler modulo $1$, puisque tous les nombres entiers sont alors considérés égaux.