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


Général

Résumé 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

Prérequis


Résumé

Dans ce chapitre, la notion de modulo est introduite. Bien qu'il s'agisse a priori d'une simple notation, cet outil se révèlera en fait très puissant et incontournable en théorie des nombres. Il est important de bien maîtriser cet outil, c'est pourquoi nous ne présentons ici que peu de théorie mais donnons plusieurs exemples détaillés de bonnes utilisations des modulos.

1. 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.

2. Propriétés

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.

3. Exemple d'utilisation

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 :

Prouver qu'il n'existe aucun $x, y \in \mathbb{Z}$ tels que $$3x^2 + 1 = 5y^2.$$

Première solution

Face à un tel problème, il est généralement de bon goût de travailler modulo un certain $n$. En effet, si on trouve un $n$ tel que $3x^2 +1$ et $5y^2$ ne sont jamais égaux modulo $n$, alors on aura en particulier montré qu'ils ne peuvent jamais être égaux tout court.
Reste à trouver quel $n$ pourrait convenir. On remarque que $5y ^2$ est toujours divisible par $5$, ou en termes modulaires, que $5y ^2$ est toujours égal à $0$ modulo $5$. Cela pouvant éventuellement faciliter les calculs, nous choississons donc de dorénavant travailler modulo $5$.
Si on parvient à montrer que $3x^2 + 1$ n'est jamais égal à $0$ (modulo $5$, mais c'est à présent sous-entendu), alors on aura résolu le problème.
Comme nous travaillons maintenant modulo $5$, il n'existe en fait plus que $5$ nombres différents, ce qui va grandement simplifier les choses ! Le nombre $x$, qui pouvait a priori prendre une infinité de valeurs, ne peut à présent en prendre que cinq : $0$, $1$, $2$, $3$ ou $4$. Il suffit donc d'évaluer $3x^2 + 1$ pour ces valeurs :
$$\begin{align}
3\cdot 0^2 + 1 &\equiv \boxed{1} \\
3\cdot 1^2 + 1 &\equiv 4 \equiv \boxed{4} \\
3\cdot 2^2 + 1 &\equiv 13 \equiv \boxed{3} \\
3\cdot 3^2 + 1 &\equiv 28 \equiv \boxed{3} \\
3\cdot 4^2 + 1 &\equiv 49 \equiv \boxed{4} \\
\end{align}$$ On constate que $3x^2+1$ n'est jamais égal à $0$, ce que nous espérions.

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$.

Deuxième solution

Nous aurions également pu décider de travailler modulo $3$, vu que $3x^2 + 1$ est toujours égal à $1$ modulo $3$.
On s'intéresse alors aux valeurs que $5y^2$ peut prendre. Il n'y a maintenant plus que $3$ valeurs possibles pour $y$, à savoir $0$, $1$ et $2$. Et on constate que pour ces valeurs de $y$, $5y^2$ prend les valeurs :
$$\begin{align}
5\cdot 0^2 &\equiv \boxed{0}\\
5\cdot 1^2 &\equiv 5 \equiv \boxed{2}\\
5\cdot 2^2 &\equiv 20 \equiv \boxed{2}
\end{align}$$ Aucune de celle-ci n'étant égale à $1$, on a à nouveau résolu le problème.

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$.

4. Critères de divisibilité

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$.

5. Théorème de Wilson

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

Un nombre $p \geq 2$ est premier si et seulement si
$$(p-1)! \equiv -1 \pmod {p}.$$

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.

Démonstration :
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 < 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$.




Des questions ? N'hésitez pas à demander de l'aide sur le forum !