La division des entiers naturels ne donne pas toujours un résultat entier, et la division euclidienne donne une meilleure approximation de ce résultat, sous la forme d’un quotient et d’un reste. On peut définir une addition et une multiplication « modulaires » sur les restes, transformations de l’addition et la multiplication classiques. En étendant la division euclidienne aux entiers relatifs, on s’aperçoit que leur soustraction se transforme en une soustraction modulaire entre restes positifs.

1. La division euclidienne des entiers naturels

1.1. Division des entiers et partages des ensembles finis

Etant données deux quantités finies \(n\) et \(b\), autrement dit deux entiers naturels, avec \(b\) bon nul, la division de \(n\) par \(b\) ne donne pas toujours un résultat exact, ce qui signifie que \(n\) n’est pas toujours divisible par \(b\). Ceci traduit la situation suivante : étant donné un lot de \(n\) objets, il n’est pas toujours possible de le partager en lots de \(b\) objets sans reste. On la traduirait de manière combinatoire sous la forme suivante : étant donné un ensemble \(E\) de \(n\) objets, il n’est pas toujours possible de décomposer \(E\) en une réunion de sous-ensembles \(B_1,B_2,\ldots,\) de \(b\) objets deux-à-deux disjoints.

1.2. Principe de la division euclidienne

La division euclidienne des entiers naturels traduit cette situation arithmétique et combinatoire en fournissant une approximation entière de la division de \(n\) par \(b\), c’est-à-dire de \(n\) en \(b\) parties égales. Cette approximation se présente sous la forme d’une décomposition \(n=b\times q+r\), qu’on appelle division euclidienne de \(n\) par \(b\). L’entier naturel \(q\) est appelé quotient de cette division, c’est le nombre maximal de sous-ensembles à \(b\) éléments (deux-à-deux disjoints) qu’on peut former dans un ensemble à \(n\) éléments : c’est donc la meilleure approximation de la division de \(n\) par \(b\). L’entier naturel \(r\) est appelé reste de la division euclidienne de \(n\) par \(b\), c’est ce qui manque éventuellement à la division pour être exacte : on a donc \(r < b\), sinon \(q\) n’est pas la meilleure approximation.

1.3. Le théorème de la division euclidienne

L’intuition nous suggère que la division euclidienne de \(n\) par \(b\) ne peut nous donner qu’un seul résultat. Effectuer cette division, c’est donc trouver les seuls nombres entiers naturels \(q\) (le quotient) et \(r\) (le reste) tels qu’on peut écrire \(n=b\times q+r\), avec \(r< b\). Mais la division euclidienne est aussi un résultat théorique, qui s’énonce proprement sous la forme suivante :

Théorème 1
Etant donnés deux entiers naturels \(n\) et \(b\) quelconques avec \(b>0\), il existe deux entiers naturels uniques \(q\) et \(r\) tels que \(a=b\times q+r\) et \(r<b\).

Donnons une idée de la démonstration de ce théorème. Soit $D$ l’ensemble des entiers naturels $d$ tels que $d\times b\leq a$. L’ensemble $D$ n’est pas vide, puisqu’il contient $0$, et tout élément $d$ de $D$ est inférieur à $a$. C’est donc un ensemble fini, qui contient un plus grand élément, notons-le $q$. Par définition de $q$, on a $b.q\leq a$, et $q+1\notin D$, donc $a<b(q+1)$. Ecrivons $r=a-bq$ : en soustrayant $bq$ (dans $\mathbb Z$) de l’inégalité précédente, par les propriétés de $<$ on obtient $0=bq-bq\leq r=a-bq<b(q+1)-bq=b$, donc on peut écrire $a=b.q+r,$ avec $0\leq r<b$ : nous avons démontré l’existence de $q$ et de $r$. Supposons maintenant que $q’$ et $r’$ sont des entiers naturels avec la même propriété, c’est-à-dire que $a=b.q’+r’$, avec $r'<b$ : on a $b.q+r=b.q’+r’$, et en soustrayant $b.q’+r$ à chaque membre, on obtient $b.q-b.q’=r’-r$ $(*)$. Comme $r,r’\leq b-1$, on a $1-b\leq -r\leq 0$, d’où $-b+1\leq r’-r\leq b-1$ et $|r’-r|<b$ par définition de la valeur absolue. De l’égalité $(*)$, on en déduit que $b.|q-q’|<b$ et en divisant par $b>0$ on obtient $|q-q’|<1$, soit $q=q’$. Il s’ensuit alors que $0=a-a=(b.q+r’)-(b.q+r)=r’-r $, donc $r=r’$ et finalement, $q$ et $r$ sont uniques. On a démontré l’unicité de $q$ et $r$.

Exemple 1
Divisons $174$ par $23$ : on a $23\times 7=161$ et $23\times 8=184$, donc le quotient de la division euclidienne de $174$ par $23$ est $7$, et le reste est $174-23\times 7=13$.

2. L’addition modulaire

2.1. Le reste de la somme de deux entiers

Quel est le reste de la division euclidienne de $m+n$ par $b$ ? Si on additionne $m$ et $n$ à partir des expressions précédentes, on obtient $m+n=b.(q_1+q_2)+(r_1+r_2)$ : cette écriture se présente comme une division euclidienne, mais il est possible de $r_1+r_2\geq b$. Par exemple, divisons $m=17$ et $n=23$ par $4$ : on a $m=4.4+1$ et $n=5.4+3$, et la somme des deux restes est $4$. L’expression précédente n’est donc pas toujours celle de la division euclidienne de $m+n$ par $b$ : on peut obtenir n’importe quel nombre compris entre $0$ et $2b-2$. En revanche, si on fait une nouvelle division euclidienne de $r_1+r_2$ par $b$, dans tous les cas on obtient le reste de la division de $m+n$ par $b$ :

Proposition 1
Si $m$ et $n$ sont deux entiers naturels et $b$ est un entier naturel $>0$, soient $r_1$ et $r_2$ les restes de la division euclidienne de $m$ et $n$ par $b$. Le reste de la division euclidienne de $m+n$ par $b$ est le reste de la division euclidienne de $r_1+r_2$ par $b$.

Le reste de la division de $m+n$ par $b$ possède une interprétation combinatoire naturelle : si $E$ est un ensemble à $m$ éléments et $F$ un ensemble à $n$ éléments et si $E$ et $F$ sont disjoints, alors on peut trouver $q_1$ sous-ensembles de $E$, et $q_2$ sous-ensembles de $F$, à $b$ éléments. Mais les $r_1$ éléments restant dans $E$ et les $r_2$ éléments restant dans $F$ peuvent éventuellement former un ensemble supplémentaire à $b$ éléments.

2.2. L’addition modulo une base de division

Ainsi, pour trouver le reste de la division euclidienne de la somme de deux entiers naturels par un entier naturel $b>0$, il suffit de savoir le faire sur les restes possibles de cette division, qui sont les entiers naturels de $0$ à $b-1$, soit les nombres $0,1,\ldots,b-1$. Ceux-ci forment un ensemble qu’on note ici $[[0,b-1]]$ (segment de nombres entiers), et le calcul des restes de leurs somme est en quelque sorte une nouvelle addition « modulo $b$ » : si $x,y\in [[0,b-1]]$, on définit $x+y$ « modulo $b$ », comme le reste de la division euclidienne de $x+y$ par $b$. Pour ne pas confondre cette opération et son résultat avec la somme ordinaire, nous l’écrirons $x\oplus y$.

Exemple 2
Par exemple, soit $b=6$. On a $3\oplus 2=5$, puisque $3+2=5<6$ (donc $5$ est le reste de la division de $3+2$ par $6$). En revanche, on a $4\oplus 5=3$, puisque $4+5=6.1+3$ est la division euclidienne de $9=4+5$ par $6$.

Ainsi, alors que la somme $x+y$ de deux restes $x,y\in [[0,b-1]]$ est un entier naturel dans l’ensemble $\{0,\ldots,2b-2\}=[[0,b-2]]$, la somme modulaire $x\oplus y$ est un entier qui reste compris entre $0$ et $b-1$.

2.3. Propriétés de l’addition modulaire

Si nous avons appelé l’opération qui associe à deux restes $x$ et $y$ modulo $b>0$ une addition modulaire, c’est parce qu’elle possède toutes les propriétés élémentaires de l’addition des entiers naturels, résumées dans l’énoncé suivant :

Proposition 2
Si $x,y$ et $z$ sont trois entiers naturels de l’ensemble $[[0,b-1]]$, alors on a :
i) $x\oplus 0=x$
ii) $x\oplus y=y\oplus x$
iii) $x\oplus (y\oplus z)=(x\oplus y)\oplus z$.

Cette proposition se démontre en écrivant les divisions euclidiennes de $x+y$, de $x+(y\oplus z)$ et $(x\oplus y)+z$ et en utilisant l’unicité du quotient et du reste dans la division euclidienne.

3. La multiplication modulaire

3.1. Le reste du produit

Nous pouvons poser, à propos du produit $m.n$ de deux entiers naturels $m$ et $n$, la même question que pour leur somme : quel est le reste de la division euclidienne de $m.n$ par $b>0$, en fonction des restes de $m$ et de $n$ ? Si nous écrivons les divisions euclidiennes respectives de $m$ et $n$ sous la forme $m=q_1.b+r_1$ et $n=q_2.b+r_2$, nous obtenons $m.n=q_1q_2.b^2+q_1r_2.b+q_2r_1.b+r_1.r_2=(q_1q_2b+q_1r_2+q_2r_1).b+r_1.r_2$. Comme pour l’addition, en général on peut avoir $r_1r_2\geq b$, donc $r_1.r_2$ n’est pas toujours le reste de la division de $m.n$ par $b$. Par exemple, divisons $19$ et $34$ par $7$ : on a $19=2.7+5$ et $34=4.7+6$, et le produit des restes est donc $6.5=30\geq 7$. Puisqu’on multiple les restes dans ce cas, le résultat peut être n’importe quel nombre compris entre $0$ et $(b-1)^2$. Mais comme pour l’addition, on peut démontrer le résultat suivant :

Proposition 3
Si $m$ et $n$ sont deux entiers naturels et $b$ est un entier naturel $>0$, soient $r_1$ et $r_2$ les restes de la division euclidienne de $m$ et $n$ par $b$. Le reste de la division euclidienne de $m\times n$ par $b$ est le reste de la division euclidienne de $r_1\times r_2$ par $b$.

3.2. La multiplication modulo une base de division

Ainsi, il est également possible de définir une multiplication modulaire entre les restes de la division par $b>0$, c’est-à-dire les éléments de $[[0,\ldots,b-1]]$. Tandis que la multiplication classique de deux tels éléments $x$ et $y$ est un entier naturel de l’ensemble $[[0,\ldots,(b-1)^2]]$, le produit modulaire $x\otimes y$ est un reste, c’est-à-dire un entier qui est compris entre $0$ et $b-1$. On définit $x\otimes y$ comme le reste de la division euclidienne de $x\times y$ par $b$. On peut aussi en démontrer simplement les propriétés élémentaires suivantes :

Proposition 4
Si $x,y$ et $z$ sont trois entiers naturels de l’ensemble $[[0,b-1]]$, alors on a :
o) $x\otimes 0=0$
i) $x\otimes 1=x$
ii) $x\otimes z=z\otimes x$
iii) $x\otimes (y\otimes z)=(x\otimes y)\otimes z$
iv) $x\otimes (y\oplus z)=(x\otimes y)\oplus (x\otimes z)$

Dans la table suivante nous avons représenté en exemple la multiplication des entiers $0,1,2,3,4$ modulo $5$ :

3.3. La « préservation » de la structure arithmétique de l’ensemble $\mathbb N$

Tout ceci montre qu’il existe une relation subtile entre l’addition et la multiplication dans $\mathbb N$ d’une part, l’addition et la multiplication modulo $b>0$ dans $[[0,b-1]]$ d’autre part. On peut conceptualiser cette relation en définissant une fonction « reste modulo $b$ » comme suit. A tout entier naturel $n$, on lui associe son reste dans la division euclidienne modulo $b$, qu’on note $f(n)$ : ceci définit donc une fonction ou application de l’ensemble $\mathbb N$ dans l’ensemble $[[0,b-1]]$, ce qu’on écrit $f:\mathbb N\to [[0,b-1]]$. On peut alors résumer ce qu’on a dit jusqu’à ici sous la forme suivante :

Théorème 1
L’application $f$ « préserve » l’addition et la multiplication, autrement dit, pour tous $m,n\in\mathbb N$, on a :
i) $f(m+n)=f(m)\oplus f(n)$
ii) $f(m\times n)=f(m)\otimes f(n)$.

Autrement dit, l’opération qui consiste à prendre le reste d’un entier naturel $m$ dans la division par $b$ donné, transforme l’addition $+$ des entiers naturels en l’addition $\oplus$ modulo $b$, et la multiplication $\times$ des entiers naturels en la multiplication $\otimes$ modulo $b$. Cette idée est à la racine de la théorie des structures mathématiques, qui sont des ensembles auxquels on adjoint des éléments, ensembles et opérations particuliers. Ces structures permettent d’approfondir considérablement notre compréhension des objets mathématiques, et d’associer des objets similaires dans une même théorie. Ici, la structure formée par l’ensemble $\mathbb N$ et les opérations $+$ et $\times$ est similaire à la structure formée par l’ensemble $[[0,b-1]]$ et les opérations $\oplus$ et $\otimes$.

4. Division des entiers relatifs et soustraction modulaire

4.1. Prolongement de la division euclidienne à l’ensemble $\mathbb Z$

Bien que les nombres entiers relatifs ne représentent pas des quantités, il est possible d’étendre la division euclidienne des entiers naturels aux entiers relatifs : il faudra donc en donner une autre interprétation. Cette division s’énonce théoriquement de la manière suivante :

Théorème 2
Pour tous entiers relatifs $n$ et $b$ avec $b>0$, il existe d’uniques nombres entiers relatifs $q$ et $r$ tels que $n=b\times q+r$ et $0\leq r< b$.

Autrement dit, la « base » de division reste ici un entier naturel non nul, et le résultat est valable si on impose aussi au reste d’être positif. La démonstration de ce théorème n’est pas difficile, et repose sur la division euclidienne des entiers naturels : si $n\geq 0$, alors le résultat est déjà connu dans ce cas. Il ne reste donc qu’à démontrer le cas où $n<0$ : puisqu’alors $-n>0$, on peut faire la division euclidienne de $-n$ par $b$ ! On peut écrire $-n=b\times q+r$ avec $0\leq r<b$, d’où $n=b\times (-q)+(-r)$, et on distingue deux cas. Si $r=0$, on a $n=b\times (-q)$, donc on a trouvé un quotient, $-q$, et un reste, $0$. Mais si $r>0$, l’écriture précédente ne convient pas : il nous faut réécrire $n=b\times (-q)-b+b-r=b\times (-q-1)+(b-r)$ et cette fois, on a $0\leq b-r<b$, donc a trouvé un quotient, $-q-1$, et un reste, $b-r$. L’unicité du quotient et du reste se démontre alors comme pour la division des entiers naturels.

Exemple 3
Reprenons la division de l’exemple 1 : on a $174=23\times 7+13$, donc $-174=23\times (-7)-13. Pour obtenir la division euclidienne de $-174$ par $23$, nous devons donc ajouter $23$ au reste et soustraire $1$ au quotient, soit réécrire $-174=23\times (-8)+10$ : le quotient est $-8$, le reste est $10$.

4.2. Interprétation géométrique de la division des entiers relatifs

L’interprétation combinatoire initiale de la division euclidienne n’est plus valable pour les entiers relatifs. Toutefois, on peut en donner une interprétation géométrique, en considérant qu’elle fournit une approximation entière de la division de $n$ par $b$, c’est-à-dire du nombre rationnel représenté par la fraction $n/b$. En effet, en écrivant $n=b\times q+r$ le résultat de la division d’un entier relatif $n$ par $b>0$, on peut diviser tous les termes de l’équation par $b$ dans l’ensemble $\mathbb Q$ des nombres rationnels. On obtient $n/b=q+r/b$, avec $q\in\mathbb Z$ et $0\leq r/b<1$. Autrement dit, on peut reformuler ainsi la division euclidienne des entiers relatifs :

Corollaire 1
Pour tout nombre rationnel $x$, il existe un unique entier relatif $m$ et un unique nombre rationnel $y$ tels que $x=m+y$ avec $0\leq y<1$.

Le nombre entier relatif $m$ du corollaire, soit le nombre $q$ de la division précédente, est ce qu’on appelle la partie entière du nombre rationnel $x$, tandis que $y$ est sa partie fractionnaire. Ces notions s’étendent aux nombres réels pour effectuer des mesures d’une grandeur dans une unité.

4.3. La soustraction modulaire

Il n’est pas toujours possible de soustraire deux entiers naturels $m$ et $n$ (on ne peut soustraire $n$ à $m$ que si $n\leq m$), et c’est essentiellement pour obtenir une telle soustraction qu’on construit les entiers relatifs : la soustraction est donc définie sur l’ensemble $\mathbb Z$ à partir de l’idée même qui en fournit la construction. Nous pourrions envisager faire la même chose avec la soustraction modulaire définie sur les restes $0,\ldots,b-1$ de la division euclidienne par un entier $b>0$. La même construction est en effet possible, mais elle est inutile, parce qu’on dispose automatiquement d’une soustraction modulaire associée à $\oplus$, puisque tout élément $x$ de $[[0,b-1]]$ possède déjà un opposé additif. En effet, si $0$ est son propre opposé additif puisque $0+0=0$, et si $x>0$, comme $x<b$ il existe un unique entier naturel $z$ tel que $x+z=b$ et on démontre qu’on a aussi $z\in [[0,b-1]]$ : puisque le reste de la division de $b$ par $b$ est $0$, on a $x\oplus z=0$. En notant alors $z=\ominus x$, on peut soustraire $y\in [[0,b-1]]$ quelconque à $x$ en posant $x\ominus y=x\oplus(\ominus y)$. Cette soustraction possède les mêmes propriétés élémentaires que la soustraction dans $\mathbb Z$, et notamment son rapport à la multiplication :

Proposition 5
Pour tout $x\in [[0,b-1]]$, on a $(\ominus 1)\otimes x=\ominus x$.

4.4. Préservation de la structure arithmétique de l’ensemble $\mathbb Z$

Ainsi, la division euclidienne des entiers naturels par $b>0$ produit déjà sur l’ensemble $[[0,b-1]]$ toute la « structure arithmétique » élémentaire qu’on trouve dans l’ensemble $\mathbb Z$. Si on interprète celle-ci comme la donnée des opérations d’addition, de multiplication et de soustraction sur l’ensemble $\mathbb Z$, on peut étendre l’interprétation donnée dans la section 3.3 de la division euclidienne des entiers naturels. Si on définit une fonction $g:\mathbb Z\to [[0,b-1]]$, qui associe à un entier relatif quelconque $n$ le reste $g(n)$ de la division euclidienne de de $n$ par $b$, on peut en effet démontrer le

Théorème 3
L’application $g$ « préserve » l’addition, la multiplication, et la soustraction, autrement dit, pour tous $m,n\in\mathbb Z$, on a :
i) $g(m+n)=g(m)\oplus g(n)$
ii) $g(m-n)=g(m)\ominus g(n)$
ii) $g(m\times n)=g(m)\otimes g(n)$.

Pour cette raison, on note parfois $\mathbb Z_b$ la structure formée de l’ensemble $[[0,b-1]]$ des restes modulo $b$ et des opérations $\oplus,\ominus$ et $\otimes$, qui s’interprète dans le cadre de la théorie des anneaux, un type particulier et ubiquitaire de structure mathématique qui permet notamment de formaliser la notion linguistique d’équation à partir de la notion mathématique de polynôme.

Retrouvez l’article en vidéo sur MATHESIS, la chaîne YouTube :