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

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