Section : Cours
Avant : Congruences
Après : Entraînement

$ \mathbb{Z}/n\mathbb{Z}$

En apparence, cette section est consacrée à un formalisme assez gratuit consistant à remplacer l'écriture :

$\displaystyle a\equiv b [n],$

par l'écriture équivalente :

$\displaystyle \mathfrak{cl}(a)= \mathfrak{cl}(b)$   dans$\displaystyle \mathbb{Z}/n\mathbb{Z}, $

où $ \mathfrak{cl}$ est l'abréviation de «classe». Maigre progrès en apparence ! Toutefois, comme des exemples judicieusement choisis le montreront en fin de section, on a fait plus qu'un simple changement de notations : on a construit un pont entre ce chapitre et le chapitre précédent, pont par lequel on pourra rapatrier des résultats connus sur les groupes pour effectivement affiner notre connaissance des entiers.

Définition 7   Soit $ n\geqslant 1$ un entier fixé. On appelle $ \mathbb{Z}/n\mathbb{Z}$ l'ensemble-quotient de $ \mathbb{Z}$ par la relation d'équivalence «est congru à» (modulo $ n$).

Exemple 3   Pour $ n=2$, soit $ a$ un entier. Si $ a$ est pair, la classe d'équivalence $ \mathfrak{cl}(a)$ pour la relation de congruence modulo $ 2$ est l'ensemble $ P$ de tous les nombres pairs ; si $ a$ est impair, $ \mathfrak{cl}(a)$ est l'ensemble $ I$ de tous les nombres impairs, et finalement $ \mathbb{Z}/2\mathbb{Z}=\{I,P\}.$

Proposition 4   Pour tout $ n\geqslant 1$, $ \mathbb{Z}/n\mathbb{Z}$ possède exactement $ n$ éléments.

Démonstration : Montrons tout d'abord que $ \mathbb{Z}/n\mathbb{Z}=\{\mathfrak{cl}(0),\mathfrak{cl}(1),\ldots,\mathfrak{cl}(n-1)\}$, d'où on déduit aussitôt que $ \mathbb{Z}/n\mathbb{Z}$ possède au plus $ n$ éléments.

Soit $ x$ un élément de $ \mathbb{Z}/n\mathbb{Z}$ ; il existe alors $ a\in\mathbb{Z}$ tel que $ x=\mathfrak{cl}(a)$. Effectuons la division euclidienne de $ a$ par $ n$, soit $ a=nq+r$ ; on voit alors que $ a\equiv r [n]$ ou encore que $ x=\mathfrak{cl}(a)=\mathfrak{cl}(r)$. Mais $ 0\leqslant r<n$, donc on a bien prouvé que $ x$ était dans l'ensemble proposé.

Montrons maintenant que ces $ n$ éléments sont deux à deux distincts, prouvant ainsi que $ \mathbb{Z}/n\mathbb{Z}$ possède au moins $ n$ éléments.

Soit $ a$ et $ b$ deux entiers distincts avec $ 0\leqslant a <n$ et $ 0\le b<n$. Des inégalités $ 0\leqslant a$ et $ b<n$ on déduit que $ -n<b-a$ ; des inégalités $ a<n$ et $ 0\leqslant b$ on déduit que $ b-a<n$ et de l'hypothèse $ a\not=b$ on déduit que $ b-a\not=0$. On en conclut que $ a\not\equiv b [n]$, c'est-à-dire que $ \mathfrak{cl}(a)$ et $ \mathfrak{cl}(b)$ sont deux éléments distincts de $ \mathbb{Z}/n\mathbb{Z}$.

On a donc bien prouvé que $ \mathbb{Z}/n\mathbb{Z}$ possède exactement $ n$ éléments.$ \square$

Définition 8   Soit $ \mathfrak{cl}(a)$ et $ \mathfrak{cl}(b)$ deux éléments de $ \mathbb{Z}/n\mathbb{Z}$. On définit la somme de $ \mathfrak{cl}(a)$ et $ \mathfrak{cl}(b)$ par $ \mathfrak{cl}(a)+\mathfrak{cl}(b) =\mathfrak{cl}(a+b)$ et leur produit par $ \mathfrak{cl}(a)\times\mathfrak{cl}(b) =\mathfrak{cl}(ab)$.

Prudence ! Cette définition est aussi innocente en apparence que celles qui l'ont précédée. Et pourtant, elle pourrait n'avoir rigoureusement aucun sens.

En effet, la définition de la somme de deux éléments $ x$ et $ y$ de $ \mathbb{Z}/n\mathbb{Z}$ nécessite implicitement de les mettre préalablement sous forme $ x=\mathfrak{cl}(a)$ et $ y=\mathfrak{cl}(b)$. Mais il y a plusieurs façons de les mettre sous cette forme ! Il faut donc vérifier que la définition ne dépend pas du choix fait dans cette phase préparatoire. Pour montrer à quel point c'est indispensable, donnons une


Fausse définition (buggée) Soit $ \mathfrak{cl}(a)$ et $ \mathfrak{cl}(b)$ deux éléments de $ \mathbb{Z}/n\mathbb{Z}$. On dira que $ \mathfrak{cl}(a)\le\mathfrak{cl}(b)$ lorsque $ a\leqslant b$.


Il est facile de comprendre pourquoi cette «définition» est bonne pour la corbeille à papier : dans $ \mathbb{Z}/3\mathbb{Z}$, prenons $ x=\mathfrak{cl}(0)$ et $ y=\mathfrak{cl}(2)$. En les écrivant ainsi, la «définition»  nous donne : $ x\leqslant y$. Mais on peut aussi écrire $ x=\mathfrak{cl}(3)$ et comme précédemment $ y=\mathfrak{cl}(2)$. En s'y prenant ainsi, $ y\leqslant x$. Cette «définition» n'a donc en fait aucun sens.


Sermon (ou : Prudence II, le retour) Malgré ses dehors anecdotiques, il est indispensable de comprendre cette remarque. La fausse définition et la bonne sont semblables formellement, alors que l'une est absurde et l'autre non. Fin du sermon.


Procédons donc à cette indispensable vérification. Soit $ x=\mathfrak{cl}(a)=\mathfrak{cl}(\alpha)$ et $ y=\mathfrak{cl}(b)=\mathfrak{cl}(\beta)$ deux éléments de $ \mathbb{Z}/n\mathbb{Z}$. La cohérence de la définition exige de prouver que $ \mathfrak{cl}(a+b)= \mathfrak{cl}(\alpha+\beta)$. La vérification est alors évidente $ (\alpha+\beta)-(a+b)=(\alpha - a)+(\beta-b)$ étant un multiple de $ n$ parce que $ \alpha-a$ et $ \beta-b$ le sont tous les deux. De même $ \mathfrak{cl}(ab)=\mathfrak{cl}(\alpha\beta)$ car $ \alpha\beta-ab=\alpha \beta-\alpha b+\alpha b - ab=\alpha(\beta-b)+b(\alpha-a)$.


Ainsi au point où nous en sommes, $ \mathbb{Z}/n\mathbb{Z}$ est muni d'une addition et d'une multiplication. Traçons un exemple de tables, pour voir quelle tête elles ont. Ce sera l'exemple de $ \mathbb{Z}/5\mathbb{Z}$.

On note dans cette table et dans les suivantes $ \dot a=\mathfrak{cl}(a)$.

\begin{displaymath}\begin{array}{\vert c\vert\vert c\vert c\vert c\vert c\vert c... ...t 0&\dot 4&\dot 3&\dot 2&\dot 1 \hline \end{array} \quad\quad\end{displaymath}    

Après la présentation de l'objet, un peu de théorie à son sujet.

Proposition 5   Pour tout $ n\geqslant 1$, $ \mathbb{Z}/n\mathbb{Z}$ est un anneau commutatif.

Démonstration : Elle est d'un ennui mortel, et ne présente aucune difficulté. Pour en faire un tout petit bout, montrons que l'addition est associative : soit $ x$, $ y$ et $ z$ trois éléments de $ \mathbb{Z}/n\mathbb{Z}$. On peut les écrire sous forme $ x=\mathfrak{cl}(a)$, $ y=\mathfrak{cl}(b)$, $ z=\mathfrak{cl}(c)$. Vu la définition de l'addition dans $ \mathbb{Z}/n\mathbb{Z}$, on a alors $ (x+y)+z=(\mathfrak{cl}(a)+\mathfrak{cl}(b))+\mathfrak{cl}(c)= \mathfrak{cl}(a+... ...athfrak{cl}(b+c) =\mathfrak{cl}(a)+(\mathfrak{cl}(b)+\mathfrak{cl}(c))=x+(y+z).$

Et toutes les vérifications seraient de ce genre. Nous décidons donc de les laisser au lecteur.$ \square$

Plus intéressant et légèrement plus subtil est le résultat suivant.

Théorème 7   Pour tout $ n\geqslant 1$, $ \mathbb{Z}/n\mathbb{Z}$ est un corps commutatif si et seulement si $ n$ est un nombre premier.

Démonstration : Montrons tour à tour les deux sens de l'équivalence.


Preuve de l'implication directe. On va montrer cette implication par contraposition. Supposons donc que $ n$ n'est pas premier, et montrons que $ \mathbb{Z}/n\mathbb{Z}$ n'est pas un corps commutatif (on verra même en passant que ce n'est même pas un anneau intègre).


Traitons à part le cas, «stupide», où $ n$ vaudrait $ 1$. Dans ce cas, $ \mathbb{Z}/1\mathbb{Z}$ ne possède qu'un élément, donc n'est pas un corps commutatif.

Examinons le cas, significatif, où $ n$ n'est pas premier, mais n'est pas non plus égal à $ 1$. Dans ce cas, on peut écrire $ n=ab$, où $ 1<a<n$ et $ 1<b<n$. Dans l'anneau $ \mathbb{Z}/n\mathbb{Z}$, on obtient alors la relation $ \mathfrak{cl}(n)=\mathfrak{cl}(a)\mathfrak{cl}(b)$, soit $ \mathfrak{cl}(a)\mathfrak{cl}(b)=\mathfrak{cl}(0)$. Pourtant, au vu des inégalités vérifiées par $ a$ et $ b$, ni $ \mathfrak{cl}(a)$ ni $ \mathfrak{cl}(b)$ n'est nul. Donc $ \mathbb{Z}/n\mathbb{Z}$ n'est pas intègre, et a fortiori n'est pas un corps commutatif.

On a bien prouvé dans les deux cas que $ \mathbb{Z}/n\mathbb{Z}$ n'est pas un corps commutatif.


Preuve de l'implication inverse. Supposons $ n$ premier, et montrons que $ \mathbb{Z}/n\mathbb{Z}$ est alors un corps commutatif.


Nous savons déjà que la multiplication sur $ \mathbb{Z}/n\mathbb{Z}$ est commutative.

Comme $ \mathbb{Z}/n\mathbb{Z}$ possède $ n$ éléments, il en possède au moins deux.

Soit $ x$ un élément non nul de $ \mathbb{Z}/n\mathbb{Z}$. On peut écrire $ x=\mathfrak{cl}(a)$ pour un entier $ a$ dans l'ensemble $ \{1,\ldots,n-1\}$. Puisque $ n$ est premier, $ a$ ne possède d'autre diviseur positif commun avec $ n$ que $ 1$ et donc $ a$ et $ n$ sont premiers entre eux. Il existe donc deux entiers relatifs $ s$ et $ t$ tels que $ 1=sa+tn$. En passant aux classes d'équivalence, on obtient : $ \mathfrak{cl}(1)= \mathfrak{cl}(s)\mathfrak{cl}(a)+\mathfrak{cl}(t)\mathfrak{cl}(n)$, soit $ \mathfrak{cl}(1)= \mathfrak{cl}(s)\mathfrak{cl}(a)+\mathfrak{cl}(t)\mathfrak{cl}(0)=\mathfrak{cl}(s)x$.

On a donc trouvé un inverse de $ x$, à savoir $ \mathfrak{cl}(s)$.

Finalement, $ \mathbb{Z}/n\mathbb{Z}$ est donc bien un corps commutatif.$ \square$

Remarque On retiendra de cette démonstration la technique pratique de calcul de l'inverse d'un élément non nul de $ \mathbb{Z}/n\mathbb{Z}$ : écrire une identité de Bézout entre un représentant de cet élément et $ n$, et redescendre aux classes d'équivalence.


Et voilà, on sait tout. Reste à donner quelques illustrations afin de convaincre de l'utilité de l'introduction de cette notion abstraite.

Exemple 4   Résoudre dans $ \mathbb{Z}$ l'équation suivante, d'inconnue $ x$ :

$\displaystyle 24x+5\equiv 0 [137].$

On peut traiter cet exemple avec ou sans usage de $ \mathbb{Z}/137\mathbb{Z}$. Faisons les deux successivement ; on constatera que les énoncés simples sur les propriétés algébriques de $ \mathbb{Z}/137\mathbb{Z}$ remplacent avantageusement les techniques, il est vrai elles aussi simples, d'arithmétique classique.


Première résolution (sans $ \mathbb{Z}/137\mathbb{Z}$)

Remarquons que $ 137$ est premier, et donc que $ 137$ et $ 24$ sont premiers entre eux ; cherchons à écrire une identité de Bézout entre 137 et 24 ; en utilisant l'algorithme décrit plus haut, on découvre que :

$\displaystyle 1=40\times 24-7\times 137,$

d'où on déduit (par une simple multiplication par $ 5$) que :

$\displaystyle 5=200\times 24-35\times137.$

Reportons cette identité dans l'équation, qui devient donc :

$\displaystyle 24x+200\times 24-35\times137\equiv0 [137]. $

À son tour, cette équation est équivalente à la condition suivante :

$\displaystyle 24(x+200)\equiv0 [137], $

qui signifie que 137 divise $ 24(x+200)$, donc, en utilisant le lemme de Gauss puisque 137 et 24 sont premiers entre eux, que 137 divise $ x+200$. Finalement, $ x$ est solution si et seulement si $ x+200\equiv 0 [137]$, c'est-à-dire $ x\equiv - 200 [137]$, c'est-à-dire $ x\equiv 74 [137]$.


Deuxième résolution (avec $ \mathbb{Z}/137\mathbb{Z}$)

Remarquons que $ 137$ est premier, et donc que $ \mathbb{Z}/137\mathbb{Z}$ est un corps commutatif. Faisons tous les calculs dans ce corps.

L'équation proposée se réécrit $ \mathfrak{cl}(24)\mathfrak{cl}(x)+\mathfrak{cl}(5)=\mathfrak{cl}(0)$, soit $ \mathfrak{cl}(24)\mathfrak{cl}(x)=-\mathfrak{cl}(5)$, soit $ \mathfrak{cl}(x)=-\mathfrak{cl}(5)(\mathfrak{cl}(24))^{-1}$.

Calculons donc $ (\mathfrak{cl}(24))^{-1}$ ; pour cela nous connaissons la bonne méthode : écrire une identité de Bézout entre $ 24$ et $ 137$, à savoir

$\displaystyle 1=40\times 24-7\times 137,$

puis redescendre aux classes d'équivalence dans $ \mathbb{Z}/137\mathbb{Z}$ : $ \mathfrak{cl}(1)=\mathfrak{cl}(40)\cdot\mathfrak{cl}(24),$ soit : $ (\mathfrak{cl}(24))^{-1}=\mathfrak{cl}(40).$

On en conclut que l'équation proposée équivaut à :

$\displaystyle \mathfrak{cl}(x)=-\mathfrak{cl}(5)(\mathfrak{cl}(24))^{-1}= -\mathfrak{cl}(5)\times\mathfrak{cl}(40)=-\mathfrak{cl}(200)=\mathfrak{cl}(74)\;. $

Exemple 5   Résoudre dans $ \mathbb{Z}$ l'équation suivante, d'inconnue $ x$ :

$\displaystyle x^4\equiv81 [73].$

Là aussi, écrire deux solutions serait possible, mais celle utilisant $ \mathbb{Z}/73\mathbb{Z}$ est tellement plus agréable à écrire que l'on s'en contentera.

Tout d'abord, l'équation s'écrit $ x^{4}-81\equiv0 [73]$ et, dans $ \mathbb{Z}$,

$\displaystyle x^{4}-81=(x^{2}-9)(x^{2}+9)=(x-3)(x+3)(x^{2}+9). $

Dans $ \mathbb{Z}/73\mathbb{Z}$, l'équation s'écrit donc

$\displaystyle (\mathfrak{cl}(x)-\mathfrak{cl}(3))(\mathfrak{cl}(x)+\mathfrak{cl}(3)) (\mathfrak{cl}(x)^{2}+\mathfrak{cl}(9))=\mathfrak{cl}(0). $

Mais $ \mathfrak{cl}(9)=-\mathfrak{cl}(64)$ donc

$\displaystyle \mathfrak{cl}(x)^{2}+\mathfrak{cl}(9)=\mathfrak{cl}(x)^{2}-\mathf... ...}(64)= (\mathfrak{cl}(x)-\mathfrak{cl}(8))(\mathfrak{cl}(x)+\mathfrak{cl}(8)). $

Finalement, en utilisant $ \mathfrak{cl}(8)=-\mathfrak{cl}(65)$ et $ \mathfrak{cl}(3)=-\mathfrak{cl}(70)$, on voit que l'équation de départ s'écrit

$\displaystyle (\mathfrak{cl}(x)-\mathfrak{cl}(3))(\mathfrak{cl}(x)-\mathfrak{cl... ...cl}(x)-\mathfrak{cl}(8))(\mathfrak{cl}(x)-\mathfrak{cl}(65))=\mathfrak{cl}(0), $

soit $ \mathfrak{cl}(x) =\mathfrak{cl}(3)$ ou $ \mathfrak{cl}(x) = \mathfrak{cl}(8)$ ou $ \mathfrak{cl}(x) =\mathfrak{cl}(65)$ ou $ \mathfrak{cl}(x) =\mathfrak{cl}(70)$, car $ \mathbb{Z}/73\mathbb{Z}$ est un corps commutatif, donc intègre.

Les solutions de l'équation proposée sont donc

$\displaystyle x\equiv3 [73] $   ou$\displaystyle x\equiv8 [73] $   ou$\displaystyle x\equiv65 [73] $   ou$\displaystyle x\equiv70 [73]. $

Exemple 6   Résoudre dans $ \mathbb{Z}$ l'équation suivante, d'inconnue $ x$ :

$\displaystyle x^{17}\equiv3 [19].$

Là encore, on ne saurait trop recommander le passage dans $ \mathbb{Z}/19\mathbb{Z}$. L'équation s'écrit dès lors : $ \mathfrak{cl}(x)^{17}=\mathfrak{cl}(3)$. Notons $ a$ l'inconnue auxiliaire $ a=\mathfrak{cl}(x)$ et remarquons que $ \mathfrak{cl}(0)^{17}\not=\mathfrak{cl}(3)$. Il suffit donc de résoudre $ a^{17}=\mathfrak{cl}(3)$ dans $ (\mathbb{Z}/19\mathbb{Z})\setminus\{\mathfrak{cl}(0)\}$.

Mais, si $ a\not=\mathfrak{cl}(0)$, alors $ a^{17}=\mathfrak{cl}(3)$ si et seulement si $ a^{18}=\mathfrak{cl}(3)a$. Maintenant, pour tout $ a$ dans le groupe multiplicatif $ (\mathbb{Z}/19\mathbb{Z})\setminus\{\mathfrak{cl}(0)\}$, on sait que l'ordre de $ a$, qui est le nombre d'éléments du groupe $ \mathopen\langle a\mathclose\rangle $, divise le nombre d'éléments de $ (\mathbb{Z}/19\mathbb{Z})\setminus\{\mathfrak{cl}(0)\}$, c'est-à-dire $ 18$.

Ainsi, pour tout élément $ a$ de $ (\mathbb{Z}/19\mathbb{Z})\setminus\{\mathfrak{cl}(0)\}$, $ a^{18}=\mathfrak{cl}(1)$. L'équation étudiée se simplifie donc grandement en $ \mathfrak{cl}(1)=\mathfrak{cl}(3)a$, c'est-à-dire $ a=(\mathfrak{cl}(3))^{-1}$. Sa résolution se ramène donc à la recherche de l'inverse de $ \mathfrak{cl}(3)$ dans $ \mathbb{Z}/19\mathbb{Z}$ ; on écrit alors une relation de Bézout : $ 13\times3-2\times 19=1$ et on en déduit que $ (\mathfrak{cl}(3))^{-1}=\mathfrak{cl}(13)$.

Finalement les solutions de l'équation initiale sont donc

$\displaystyle x\equiv13 [19]. $

Exemple 7   Résoudre dans $ \mathbb{Z}$ l'équation suivante, d'inconnue $ x$ :

$\displaystyle x^{14}\equiv1 [19].$

Ce sont les mêmes idées que dans l'exemple précédent qui font marcher cet exercice, en un peu plus astucieux encore.

Comme dans l'exemple prédédent, on commence par passer dans $ \mathbb{Z}/19\mathbb{Z}$, où l'équation s'écrit dès lors : $ \mathfrak{cl}(x)^{14}=\mathfrak{cl}(1)$. On note $ a=\mathfrak{cl}(x)$, on remarque que $ \mathfrak{cl}(0)$ n'est pas solution, et on décide donc de résoudre $ a^{14}=\mathfrak{cl}(1)$ dans $ (\mathbb{Z}/19\mathbb{Z})\setminus\{\mathfrak{cl}(0)\}$.

Maintenant, on remarque que pour tout $ a$ de $ (\mathbb{Z}/19\mathbb{Z})\setminus\{\mathfrak{cl}(0)\}$, dire que $ a^{14}=\mathfrak{cl}(1)$ équivaut à dire que l'ordre de $ a$ divise $ 14$. Par ailleurs, comme dans l'exemple précédent, pour tout élément $ a$ de $ (\mathbb{Z}/19\mathbb{Z})\setminus\{\mathfrak{cl}(0)\}$, l'ordre de $ a$ divise $ 18$. Ainsi, l'ordre de $ a$ divise $ 14$ si et seulement s'il divise $ 14$ et $ 18$, donc si et seulement s'il divise $ \mathrm{pgcd}(14,18)=2$.

On a donc montré que pour tout $ a$ de $ (\mathbb{Z}/19\mathbb{Z})\setminus\{\mathfrak{cl}(0)\}$, $ a^{14}=\mathfrak{cl}(1)$ si et seulement si $ a^2=\mathfrak{cl}(1)$.

Cette nouvelle équation est alors très facile à résoudre : $ a^2=\mathfrak{cl}(1)$ si et seulement si $ (a+\mathfrak{cl}(1))(a-\mathfrak{cl}(1))=\mathfrak{cl}(0)$ si et seulement si $ a=\mathfrak{cl}(1)$ ou $ a=-\mathfrak{cl}(1)=\mathfrak{cl}(18)$.

Les solutions de l'équation initiale sont donc

$\displaystyle x\equiv1 [19] $   ou$\displaystyle x\equiv18 [19]. $


Section : Cours
Avant : Congruences
Après : Entraînement


         © UJF Grenoble, 2011                              Mentions légales