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

Notion de modulo

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.

On aimerait, lorsque l'on se met à travailler modulo $n$, pouvoir continuer à additionner ou multiplier des nombres comme on le fait d'habitude sur les nombres entiers. Les propriétés élémentaires suivantes nous indiquent que cela nous est généralement permis.

• Si $a \equiv b \pmod n$ et $c \equiv d \pmod n$, alors $a + c \equiv b + d \pmod n$. En effet, si $n$ divise $a-b$ et $c-d$, il divise automatiquement $a+c-(b+d)$.


• Si $a \equiv b \pmod n$ et $c \equiv d \pmod n$, alors $a - c \equiv b - d \pmod n$. Le raisonnement est identique.


• Si $a \equiv b \pmod n$ et $c \equiv d \pmod n$, alors $a c \equiv b d \pmod n$. En effet, si $n$ divise $a-b$ et $c-d$, alors il divise également $ac-bd = (a-b)\cdot c + (c-d)\cdot b$.

Lorsqu'on utilise l'addition, la soustraction ou la multiplication, on peut donc presque oublier que nous travaillons modulo $n$ et manipuler les nombres comme nous le faisions avant.
Cela n'est cependant pas aussi simple si l'on souhaite utiliser la division ! Par exemple, pour $n = 10$, on a $6 \equiv 16 \pmod{10}$ mais $3 \not \equiv 8 \pmod{10}$. On ne peut donc dans ce cas pas impunément diviser les deux membres d'une égalité par $2$.

Remarque

Nous disions plus haut que, en travaillant modulo $n$, nous pouvions désormais considérer deux nombres égaux modulo $n$ comme égaux tout court. Il s'agit là d'un raccourci de langage et il faut tout de même faire très attention en manipulant ainsi les nombres.
Pour illustrer ce danger, fixons $n = 5$. Si nous sommes en présence d'un nombre $x$, alors les propriétés précédentes nous indiquent que :

• ajouter $6$ à $x$ revient à lui ajouter $1$,
• soustraire $6$ à $x$ revient à lui soustraire $1$,
• multiplier $x$ par $6$ revient à le multiplier par $1$.

Il existe cependant un cas où nous pourrions être tenté de remplacer $6$ par $1$ alors que cela ne nous est pas permis : celui de la puissance. Modulo $5$, élever $x$ à la puissance $6$ ne revient pas à l'élever à la puissance $1$. La puissance $6$ n'est qu'une simple notation pour écrire $x \cdot x \cdot \ldots \cdot x$, où $x$ apparaît $6$ fois. Il n'y a aucune raison pour laquelle on pourrait remplacer $6$ par $1$ dans ce cas. On constate par exemple que $2^6 \equiv 64 \equiv 4 \pmod 5$ alors que $2^1 \equiv 2 \pmod 5$.
Cela dit, nous verrons dans un prochain chapitre qu'il existe une façon de remplacer une puissance par une autre plus petite correctement, grâce au théorème d'Euler-Fermat.

Il n'est pas évident de se faire immédiatement une intuition des modulos et de leur utilité. C'est pourquoi nous allons, en détails, montrer comment les modulos permettent de résoudre aisément un problème non-trivial.

Considérons le problème suivant :



Analyse : Ce que les modulos nous ont permis de montrer, c'est que le nombre $3x^2+1$ n'est jamais divisible par $5$ : il donnera toujours un reste de $1$, $3$ ou $4$ après division par $5$.


Analyse : Ici, nous avons prouvé grâce aux modulos que $5y^2$ donne toujours un reste de $0$ ou $2$ après division par $3$, alors que $3x^2 +1$ donne évidemment un reste de $1$.

L'utilisation des modulos permet également de simplifier certaines démonstrations. Nous allons, afin de vous familiariser encore plus avec cette notion, présenter en détails les critères de divisibilité par $9$ et par $11$ qui se prouvent sans peine à l'aide de l'arithmétique modulaire.

Critère de divisibilité par $9$

Il est bien connu qu'un nombre est divisible par $9$ si et seulement si la somme de ses chiffres l'est. Ce critère se démontre très facilement en travaillant modulo $9$ :

On considère le nombre $x$ dont l'écriture décimale est $a_k a_{k-1}\dots a_1 a_0$. Cela signifie que
$$x = 10^k \cdot a_k + 10^{k-1} \cdot a_{k-1} + \ldots + 10 \cdot a_1 + a_0.$$ Or, étant donné que $10 \equiv 1 \pmod 9$, il en est de même pour toutes ses puissances : $10^i \equiv 1^i \equiv 1 \pmod 9$. Dès lors, on voit que
$$ x \equiv a_k + a_{k-1} + \ldots + a_1 + a_0 \pmod 9.$$ Cela signifie que $x$ et la somme des chiffres de $x$ donnent le même reste après division par $9$. En particulier, l'un est divisible par $9$ si et seulement si l'autre l'est aussi. Il s'agit bien sûr du même raisonnement pour le critère bien connu de divisibilité par $3$.

Critère de divisibilité par $11$

Le critère de divisibilité par $11$, un peu moins connu que celui par $9$, est pourtant très similaire. Nous allons le découvrir directement par sa démonstration. On travaille évidemment modulo $11$ dans ce cas-ci :

On considère à nouveau le nombre $x$ dont l'écriture décimale est $a_k a_{k-1}\dots a_1 a_0$, d'où
$$x = 10^k \cdot a_k + 10^{k-1} \cdot a_{k-1} + \ldots + 10 \cdot a_1 + a_0.$$ Cette fois-ci, on a $10 \equiv -1 \pmod {11}$, et donc $10^i \equiv (-1)^i \pmod{11}$, ce qui signifie que
$$ x \equiv (-1)^k a_k + (-1)^{k-1} a_{k-1} + \ldots - a_1 + a_0 \pmod{11}.$$ Ainsi, $x$ et la somme alternée des chiffres de $x$ donnent le même reste après division par $11$. Pour savoir si un nombre est divisible par $11$, il suffit donc de regarder ce qu'il en est de la somme alternée de ses chiffres (en commencant par la gauche ou par la droite, ce qui ne change éventuellement que le signe du résultat).

Par exemple, le nombre $91839$ est divisible par $11$ car $9-1+8-3+9 = 22$, alors que $3576$ ne l'est pas car $3-5+7-6 = -1$.

Pour conclure ce chapitre, énonçons le théorème de Wilson :


Ce théorème est en fait un critère permettant de déterminer si un nombre est premier ou non. Cela peut paraître exceptionnel (on dit généralement qu'il est très difficile de déterminer si un nombre est premier), mais ce critère n'est en fait pas miraculeux. En effet, pour savoir si le nombre $101$ est premier, il faudrait calculer $100!$ et le diviser par $101$ pour voir si le reste obtenu est $-1$ ou non. On ne peut pas dire que cela soit très efficace, il est encore plus court de tester les différents diviseurs possibles de $101$.

Si ce théorème n'est pas utile d'un point de vue algorithmique, il arrive cependant qu'il permette de résoudre des problèmes d'olympiades, et il ne faut dès lors pas le perdre de vue.

Nous n'allons pas démontrer ce théorème entièrement : cela nécessite la connaissance des inverses modulo $p$ (que l'on introduira un peu plus tard). Un des sens de l'équivalence est cependant facile à prouver : si $(p-1)! \equiv -1 \pmod p$, alors $p$ est forcément premier. En effet, si $p$ n'était pas premier, il aurait un diviseur $q$ tel que $1 < q < p$. Le nombre $q$ apparaitrait alors dans la factorielle $(p-1)! = 1 \cdot \ldots \cdot (p-1)$, et celle-ci serait donc divisible par $q$. Cela contredit l'hypothèse, puisqu'on a supposé que $p$ (et donc $q$) divisait $(p-1)! + 1$.