Au moment d’écrire ces lignes, il est 16:00. Quelle heure sera-t-il dans \(2\) heures? Bien sûr, la réponse est \(18:00\text{.}\) Si la question avait pourtant été quelle heure sera-t-il dans \(20\) heures, la réponse n’aurait pourtant pas été \(36:00\text{,}\) mais plutôt \(12:00\text{.}\) Cet exemple représente un classique de la notion d’arithmétique modulaire. On utilise l’arithmétique modulaire dans des contextes où un aspect cyclique est présent, pour effectuer certaines formes de vérification et en cryptographie.
Dans cette section, on définit la relation de congruence modulo \(n\) et on explique les règles de calculs de l’arithmétique modulaire. On présente aussi une introduction à la cryptographie.
Lorsqu’on effectue la division d’un entier par \(2\text{,}\) les restes possibles de la forme quotient reste sont \(0\) ou \(1\text{.}\) Pour une division par \(3\text{,}\) les restes sont limités à l’ensemble \(\{0,1,2\}\text{.}\) De manière générale, le reste de la division d’un entier par \(n>0\) est un élément de \(\{0,1,\ldots, n-1\}\text{.}\) Lorsqu’on parle de la division par un entier spécifique \(n\text{,}\) il est souvent utile d’associer les entiers à leur reste de la division par \(n\text{.}\) On parle alors des classes d’équivalence modulo \(n\text{.}\)
Soit \(a,b\in \mathbb{Z}\) des entiers et \(n>0\) un autre entier positif. On dit que \(a\) est congru à \(b\) modulo \(n\) si \(a\) et \(b\) possède le même reste lors de la division par \(n\text{.}\) On peut alors écrire
\begin{equation*}
a\equiv b \mod n\text{.}
\end{equation*}
On dit alors que \(a\) et \(b\) sont dans la même classe d’équivalence modulo \(n\text{.}\) De manière générale, pour un entier \(0\leq r< n\text{,}\) on définit la classe d’équivalence à \(r\) modulo \(n\) par
\begin{equation*}
E_{r,n}=\{a\in \mathbb{Z}~ |~ a \text{ divisé par } n \text{ produit un reste de } r\}\text{.}
\end{equation*}
Dans le cas des heures de la journée, on peut dire que \(36\) est dans la même classe d’équivalence que \(12\) modulo \(24\text{.}\) C’est pourquoi \(20\) heures après \(16:00\text{,}\) il est \(12:00\text{.}\) Les classes d’équivalence établissent un élément qui les représente et associe à tout autre entier équivalent cet élément.
On considère les entiers et la division par \(5\text{.}\) On cherche à décrire en extension les classes d’équivalence modulo \(5\text{,}\) à savoir les ensembles \(E_{r,5}\) de la définition 3.3.1.
Les restes de la division par \(5\) possibles sont \(\{0,1,2,3,4\}\text{.}\) À chacun de ces restes correspond une classe d’équivalence qui contient d’autres entiers. Par exemple,\(E_{0,5}\) contient tous les nombres qui produisent un reste de \(0\) lorsque divisé par \(5\text{.}\) Ce sont les multiples de \(5\text{:}\)
Les nombres \(m\) dans \(E_{1,5}\) s’écrivent comme \(m=5q+1\text{.}\) Ce sont donc les nombres qui valent un de plus qu’un multiple de \(5\text{.}\) On aura alors
D’une manière analogue, on remarque que la classe d’équivalence \(E_{2,5}\) contient les nombres qui valent deux de plus qu’un multiple de \(5\text{,}\)\(E_{3,5}\) les nombres qui valent trois de plus qu’un multiple de \(5\) et finalement, les nombres qui valent quatre de plus qu’un multiple de \(5\) pour \(E_{4,5}\text{.}\) On a
En déterminant dans quelle classe d’équivalence un nombre se trouve, on peut obtenir l’information importante sous une forme plus standard, comme avec l’exemple de l’heure. Ceci est aussi vrai pour le mois, la journée 1
Le cas des journées est un peu plus complexe dû aux années bissextiles.
On prend comme convention d’ordonner les journées de la semaine du dimanche au samedi, avec dimanche correspondant à \(0\) et samedi à \(6\text{.}\) On commence à numéroter par \(0\) afin de correspondre aux classes d’équivalence. Ainsi, vendredi correspond à \(5\text{.}\) Comme il y a sept jours dans une semaine, on veut travailler modulo \(7\text{.}\)\(18\) jours après l’écriture, on était le jour \(5+18=23\text{.}\) En regardant le reste de \(23\) lors de la division par \(7\text{,}\) on retrouve \(2\text{,}\) ce qui signifie que \(23\equiv 2\mod 7\text{.}\) On peut donc dire que \(18\) jours plus tard, c’était l’équivalent du jour \(2\text{,}\) c’est-à-dire un mardi.
On note au passage ici que le choix de faire débuter la semaine au dimanche est arbitraire et ne change rien. Si on avait fait commencer la semaine le mercredi (donc vendredi\(=2\text{,}\) alors on aurait eu \(2+18\equiv 6\mod 7\text{,}\) ce qui donne encore le mardi.
D’une manière similaire, on pourrait associer les mois de l’année à des nombres en commençant par janvier à \(0\text{.}\) On numérote toutefois déjà les mois de \(1\) à \(12\text{,}\) allant de janvier à décembre. Dans ce cas, on peut aussi choisir décembre comme point de départ décembre. Puisque \(12\equiv 0\mod 12\text{,}\) on a équivalence. Septembre étant le neuvième mois, \(10\) mois après septembre, ce sera équivalent au \(9+10=19\equiv 7\mod 12\text{,}\) donc au septième mois, soit juillet.
On travaille modulo \(24\text{,}\) avec le début correspondant à minuit. Dans \(75\) heures, puisque \(14+75=89\) et que \(89\equiv 17\mod 24\text{,}\) on conclut que \(75\) heures après l’écriture de ces lignes, il était \(17:40\text{.}\)
L’année \(2022\) et l’année \(2023\) ne sont pas des années bissextiles. Elles contiennent donc chacun \(365\) jours. Pour trouver le jour de la semaine \(2\) ans après le \(17\) septembre \(2021\text{,}\) il suffit de travailler modulo \(7\) avec le vendredi de \(2021\text{.}\) En ajoutant les \(365+365\) journées de ces deux années, on trouve \(5+365+365=735\text{,}\) qui est congru à \(0\) modulo \(7\text{.}\) Dans deux ans, le \(17\) septembre sera donc un dimanche.
Dans les quatre années suivantes \(2021\text{,}\) il y a nécessairement une année bissextile. Celle-ci se trouve en \(2024\text{.}\) Donc pour calculer le jour de la semaine, il faut ajouter \(4\times 365+1\) jours au vendredi \((5)\) de \(2021\) et travailler encore une fois modulo \(7\text{.}\) On trouve alors \(5+4\times 365+1=1466\equiv 3\mod 7\text{.}\) Le \(17\) septembre \(2025\) sera (était?) donc un mercredi.
À partir d’ici, les choses se compliquent légèrement. La difficulté vient du fait que les mois n’ont pas tous le même nombre de jours et donc, on ne peut pas travailler modulo un entier régulier. On commence par ajouter les \(35\) jours à \(17\) pour obtenir \(35+17=52\text{.}\) Puisque septembre compte \(30\) jours, on travaillera modulo \(30\text{.}\) On apportera toutefois une précision dans la prochaine solution.
Donc, \(52\equiv 22\mod 30\text{,}\) ce qui signifie que la date \(35\) jours après le \(17\) septembre est équivalent à un \(22\) et donc, le \(22\) octobre.
Si on essaie la même chose pour trouver la date \(55\) jours après le \(17\) septembre, on trouvera \(17+55=72\equiv 12\text{.}\) On comprend assez rapidement qu’il ne peut s’agir du \(12\) octobre. Il serait logique de penser que la date est alors le \(12\) novembre, mais cela est aussi faux. L’erreur vient du fait que le prochain mois, octobre, compte \(31\) jours et non pas \(30\) comme septembre. On doit donc retrancher une journée à la date trouvée pour obtenir le \(11\) novembre.
Le cas plus général est un problème relativement difficile étant donné la dépendance avec la date de départ, le nombre de jours par mois variant d’un mois à l’autre ainsi que les années bissextiles.
Après avoir vu plusieurs exemples, il est temps de faire une mise au point sur la notation utilisée pour dénoter la congruence modulo \(n\text{.}\) Si \(a,b\) sont congrus modulo \(n\text{,}\) ils sont dits équivalents, en quelque sorte égaux, par rapport à la division par \(n\text{.}\) On ne veut toutefois pas écrire \(a=b\text{,}\) car au sens usuel de l’égalité, c’est probablement faux. Le symbole \(\equiv\) est utilisé pour dénoter l’équivalence ou la congruence entre deux objets mathématiques. Il serait par contre erroné de simplement écrire \(a\equiv b\text{,}\) puisque la congruence est dépendante du choix de \(n\text{.}\) Ainsi \(10\equiv 2\mod 8\text{,}\) mais \(10\cancel \equiv 2\mod 5\text{.}\)
Si deux entiers \(a,b\) sont dans une même classe d’équivalence, alors ils se trouvent à une distance d’un multiple de \(n\text{.}\) On a donc \(a-b=kn\) où \(k\in \mathbb{Z}\text{.}\) Ceci permet de donner une définition alternative à la congruence modulo \(n\text{.}\)
Dans un premier temps, on suppose que \(a\equiv b\mod n\) au sens de la définition 3.3.1. On tente maintenant de montrer que \(n\) divise \(a-b\text{.}\) D’une part, on sait qu’il existe \(q_1,r_1\in \mathbb{Z}\) tels que \(a=nq_1+r_1\text{.}\) De plus, on sait qu’il existe \(q_2,r_2\in \mathbb{Z}\) tels que \(b=nq_2+r_2\text{.}\) Puisque \(a\equiv b\mod n\text{,}\) on doit avoir \(r_1=r_2\text{.}\) On peut alors écrire
On suppose maintenant que \(n\mid (a-b)\) et on veut montrer que cette hypothèse entraine que \(a\equiv b\mod n\text{.}\) Si \(n\) divise \(a-b\text{,}\) alors on peut écrire \(a-b=kn\) pour un certain \(k\in \mathbb{Z}\text{.}\) Si on écrit la division de chaque côté sous la forme quotient reste, il suit du fait que \(\frac{a-b}{n}=\frac{a}{n}-\frac{b}{n}\) que la forme quotient reste du côté gauche doit s’écrire \(nq_1+r_1-(nq_2+r_2)\text{.}\) De l’autre côté, \(\frac{kn}{n}=k\) et le reste est nul. On doit donc avoir \(nq_1+r_1-(nq_2+r_2)=kn+0\) et en développant, on est forcé d’avoir \(r_1-r_2=0\text{.}\) Les nombres \(a,b\) ont donc le même reste lors de la division par \(n\) et ainsi, \(a\equiv b\mod n\text{.}\)
La grande utilité des congruences modulo vient de l’arithmétique qu’il est possible d’effectuer dans les classes d’équivalences. Afin d’illustrer par des exemples, on considère à nouveau les classes d’équivalence de la division par \(5\) établies à l’exemple 3.3.2. Si on prend deux nombres de la classe d’équivalence \(E_{0,5}\) et qu’on les additionne, par exemple \(a=5,b=15,a+b=20\text{,}\) on obtient toujours un membre de \(E_{0,5}\text{.}\) Qu’en est-il de deux membres de la classe \(E_{1,5}\text{?}\) Par exemple, avec \(a=-4,b=16,a+b=12\text{,}\) cette fois on obtient un membre de la classe \(E_{2,5}\) puisque \(12\equiv 2\mod 5\text{.}\) Dans un sens, c’est parfaitement logique puisque \(1+1=2\) et que les membres de \(E_{1,5}\) sont l’équivalent du nombre \(1\) au niveau de la division par \(5\text{.}\) Le produit se comporte aussi de cette manière. Un nombre dans \(E_{2,5}\) multiplié par un nombre dans \(E_{3,5}\) se retrouvera dans \(E_{1,5}\) puisque \(2\times 3=6\equiv 1\mod 5\text{.}\) Par exemple \(12\times -2=-24\equiv 1\mod 5\) puisque \(-24\) est un de plus qu’un multiple de \(5\text{.}\) On généralise cette idée dans la proposition suivante.
L’idée derrière cette propriété découle du fait suivant: si \(a=b\text{,}\) alors pour tout \(c\in \R\text{,}\) on a \(a+c=b+c\text{.}\) On peut toujours effectuer une même opération de part et d’autre d’une égalité et préserver celle-ci. Dans le contexte des congruences modulo \(n\text{,}\) il n’est pas nécessaire d’ajouter de chaque côté le même nombre, en autant que les ajouts soient dans la même classe d’équivalence. On démontre maintenant la première propriété.
Puisque \(a\equiv b\mod n\) et \(c\equiv d \mod n\text{,}\) on sait qu’il existe \(q_1,q_2,q_3,q_4,r_1,r_2\in \mathbb{Z}\) tels que \(a=nq_1+r_1,b=nq_2+r_1,c=nq_3+r_2\) et \(d=nq_4+r_2\text{.}\) En additionnant \(a+c\) et \(b+d\text{,}\) on trouve
Si \(r_1+r_2< n\text{,}\) alors on vient de montrer que \(a+c\) et \(b+d\) ont le même reste lorsque divisés par \(n\text{.}\) Ils sont donc congrus modulo \(n\text{.}\) Si toutefois \(r_1+r_2\geq n\text{,}\) alors il faut d’abord écrire \(r_1+r_2=n+r_3\text{.}\) Puisque \(0\leq r_1,r_2< n\text{,}\) on sait que \(r_1+r_2< 2n\) et donc \(0\leq r_3< n\text{.}\) On a alors
La deuxième propriété peut être démontrée d’une manière identique à la première, mais on choisit ici de présenter une approche différente tirant profit de la proposition 3.3.5. D’une part, si \(a\equiv b\mod n\text{,}\) alors \(a-b=k_1n\) puisque \(n\mid (a-b)\text{.}\) De même, \(c-d=k_2n\text{.}\) On peut alors écrire \(a-c=k_1n+b-(k_2n+d)\text{,}\) qui devient \(a-c=(k_1+k_2)n+b-d\text{.}\) Or cela signifie que
On regarde maintenant un des avantages de ces propriétés. En particulier, quand on travaille avec de grands nombres, on peut considérablement simplifier les calculs en utilisant les propriétés de l’arithmétique modulaire
L’idée est de décomposer le nombre \(2^{345}\) en quelque chose de plus petit et dont on connait le reste de la division par \(7\text{.}\) Dans ce cas-ci, on voit que \(345=5\times 69\) et donc \(2^{345}=(2^5)^{69}\text{.}\) Comme \(2^5=32\equiv 4\mod 7\text{,}\) la troisième propriété appliquée à répétition nous permet de dire que
Le reste de la division par \(7\) du nombre \(2^{345}\) est donc \(1\text{.}\) On note au passage qu’on aurait pu y arriver plus rapidement en divisant \(345\) par \(3\) plutôt que par \(5\) initialement.
Dans la proposition 3.3.5, il est question d’addition, de soustraction et de multiplication. Dans un chapitre où la division tient une place si importante, ne devrait-il pas y avoir une propriété de division? Par exemple, \(28\equiv 4\mod 6\) et si on divise par \(4\) de chaque côté, on obtient \(7\equiv 1\mod 6\text{,}\) qui est vrai. Mais si on considère plutôt \(10\equiv 4 \mod 6\) et qu’on divise par \(2\text{,}\) l’équivalence ne tient plus puisque \(5\cancel \equiv 2\mod 6\text{.}\) On voit donc que la situation est plus complexe qu’elle en a l’air.
D’où vient le problème? On imagine un cas général où \(ac\equiv bc\mod n\text{.}\) On peut alors dire que \(ac=bc+kn\) pour un certain \(k\in\mathbb{Z}\text{.}\) Que se passe-t-il si on divise la congruence par \(c\text{?}\) Puisque \(ac-bc=(a-b)c=kn\text{,}\) il s’en suit que \(c\mid kn\text{.}\) On ne sait toutefois pas si \(c\mid n\) ou \(c\mid k\text{.}\) En fait, ça pourrait même être ni l’un ni l’autre, par exemple \(6\mid (3\times 4)\text{,}\) mais \(6\) ne divise ni \(3\) ni \(4\text{.}\) Dans la congruence avec \(28\) et \(4\text{,}\) on a \(a=7,b=1,c=4\) et \(n=6\text{.}\) On peut alors écrire \(7\times 4=1\times 4+4\times 6\text{,}\) ce qui donne \(k=4\text{.}\) Dans ce cas, la division par \(c=4\) laisse \(n=6\) intact, d’où le fait que la congruence tient le coup après la division. Par contre pour la congruence avec \(10\) et \(4\text{,}\) on a \(a=5,b=2,c=2\) et toujours \(n=6\text{,}\) ce qui permet d’écrire \(5\times 2=2\times 2+1\times 6\text{,}\) avec \(k=1\text{.}\) Cette fois, la division par \(c=2\) touche en partie \(n=6\text{,}\) ce qui rend la congruence fausse.
Dans le pire des cas, la division par \(c\) va simplifier de \(n\) la plus grande partie commune à \(c,n\text{,}\) soit \(\pgcd{(c,n)}\text{.}\) Ceci amène à la proposition suivante.
À noter que la proposition ne dit pas que \(a\cancel \equiv b\mod n\text{.}\) On ne peut tout simplement pas en être certain. En reprenant les exemples qui précèdent la proposition ci-dessus, puisque \(7\times 4\equiv 1\times4\mod 6\text{,}\) on sait que \(7\equiv 1\mod \frac{6}{\pgcd{(4,6)}}\text{,}\) c’est-à-dire \(7\equiv 1\mod 3\text{.}\) Cela n’empêchait \(7\equiv 1\mod 6\text{.}\) Pour l’autre exemple par contre, on n’a que \(5\equiv 2 \mod \frac{6}{\pgcd{(2,6)}}\text{,}\) soit \(5\equiv 2 \mod 3\text{.}\)
En travaillant modulo \(7\text{,}\) puisque \(18\equiv 4\mod 7\text{,}\) on peut dire que \(5+18\equiv 5+4\mod 7\text{.}\) Puisque \(9\equiv 2\mod 7\text{,}\) on conclut à nouveau que \(18\) jours après l’écriture, c’était un mardi. Une autre approche consiste à dire que \(18\equiv -3 \mod 7\) et donc \(5+18\equiv 5-3 \mod 7\) et ainsi, on retrouve le mardi.
Puisque \(10\equiv -2 \mod 12\text{,}\) plutôt que d’additionner \(10\) mois, on peut soustraire \(2\) mois au mois actuel et trouver la réponse, soit \(9-2=7\) et donc, juillet.
En travaillant modulo \(24\text{,}\) on a \(75\equiv 3\mod 24\) et donc, \(75\) heures après l’écriture de ces lignes est équivalent en termes d’heures à \(3\) heures après. Il était donc \(17:40\text{.}\)
Tel que discuté précédemment, il n’y a pas d’année bissextile en \(2022\) ni en \(2023\text{.}\) Ces deux années comptent donc pour \(730\) jours. Puisque \(730\equiv 2\mod 7\text{,}\) la journée de la semaine deux ans après l’écriture de ces lignes est un dimanche.
Les quatre années comptant ici pour \(1461\) jours et que \(1461\equiv 5\mod 7\) et que \(5\equiv -2 \mod 7\text{,}\) le jour de la semaine \(4\) ans après l’écriture de ces lignes est un mercredi.
Il est parfois pratique de visualiser les opérations d’addition et de multiplication à l’aide d’une table. À titre d’exemple, voici la table de multiplication pour l’arithmétique usuelle:
Puisque tous les entiers ont leur équivalent modulo \(5\) dans l’ensemble \(\{0,1,2,3,4\}\text{,}\) il n’est pas nécessaire de construire une table plus grande.
Sous-section3.3.3Résolution d’équations en congruence modulo
On considère l’équation \(3x-2=4\text{.}\) Cette équation se résout en envoyant le \(-2\) à droite et en divisant par \(3\text{,}\) obtenant ainsi \(x=2\text{.}\) Qu’en est-il de l’équation \(3x-2\equiv 4\mod 5\) maintenant? Peut-on trouver des solutions à cette équation? Comme ici la valeur du modulo est petite, on pourrait tester tous les cas possibles (modulo \(5\)) et voir que \(x=2\) est encore une solution. Bien sûr, n’importe quel autre nombre dans la classe d’équivalence de \(2\) fera aussi l’affaire. Par exemple, puisque \(12\equiv 2\mod 5\text{,}\) on peut vérifier que \(3\times 12-2=34\equiv 4\mod 5\text{.}\)
On note que dans l’équation \(3x\equiv 6\mod 5\) obtenue dans la résolution, on peut diviser de chaque côté par \(3\) puisque \(\pgcd{(3,5)}=1\) (proposition 3.3.8). On n’a donc pas à modifier le modulo. On regarde d’autres exemples.
Pour la première congruence, on ne peut pas directement diviser par \(5\) puisque \(5\not\mid 12\text{.}\) Mais on peut toutefois ajouter un élément de la classe d’équivalence de \(0\) à droite sans changer la véracité de la congruence, selon la proposition 3.3.6. En ajoutant \(13\equiv 0\mod 13\text{,}\) on obtient \(5x\equiv (12+13)\mod 13\text{,}\) qui revient à \(5x\equiv 25\mod 13\text{.}\) Maintenant qu’on a \(5\mid 25\) et que \(\pgcd{(5,13)}=1\text{,}\) on peut diviser par \(5\) et obtenir \(x\equiv 5\mod 13\text{.}\) Les solutions sont donc tous les nombres congrus à \(5\) modulo \(13\text{.}\)
Pour la seconde congruence, il peut être une bonne idée de réduire dans un premier temps modulo \(9\) les membres de chaque côté de l’équation. En effet, si \(122=9q_1+r_1\) et \(83=9q_2+r_2\text{,}\) alors la congruence peut s’écrire de manière plus simple \(r_1x\equiv r_2\mod 9\text{.}\) Puisque \(122\equiv 5 \mod 9 \) et \(83\equiv 2\mod 9\text{,}\) la congruence peut s’écrire \(5x\equiv 2\mod 9\text{.}\) Cette fois, ajouter \(9\) ne sera pas suffisant, mais si on ajoute \(18\equiv 0\mod 9\text{,}\) on obtient \(5x\equiv 20\mod 9\) et en divisant, on conclut que \(x\equiv 4\mod 9\text{.}\) Les solutions sont donc tous les nombres congrus à \(4\) modulo \(9\text{.}\)
Dans cet exemple, peu importe combien de multiples de \(8\) on ajoute à \(3\text{,}\) on n’obtiendra jamais un nombre pair qui permettra la division par \(2\text{.}\) Cette congruence en fait n’a pas de solutions. Lorsqu’on multiplie \(2\) par un entier, on obtient un nombre pair, qui ne peut pas être congru à \(3\) modulo \(8\text{.}\)
Puisqu’il est possible qu’une congruence ne possède pas de solutions, il serait intéressant de savoir quand des solutions seront possibles. En fait, on peut établir un critère pour savoir quand la congruence n’aura pas de solutions.
Soit \(a,b,n\in \mathbb{Z}\) avec \(a,n\) différents de \(0\text{.}\) Si \(\pgcd{(a,n)}\not \mid b\text{,}\) alors la congruence \(ax\equiv b\mod n\) ne possède pas de solutions.
On suppose que \(s\) est une solution à la congruence. Cela signifie que \(as\equiv b\mod n\) ou de manière équivalente, \(n\mid (as-b)\text{.}\) On réécrit pour obtenir \(as-b=kn\) pour un certain \(k\in \mathbb{Z}\text{.}\) On divise maintenant cette équation par \(\pgcd{(a,n)}\text{.}\) On obtient alors \(r-\frac{b}{\pgcd{(a,n)}}=t\) où \(r,t\) sont des entiers. Or puisque \(\pgcd{(a,n)}\not \mid b\text{,}\) le terme \(\frac{b}{\pgcd{(a,n)}}\) lui, n’est pas entier. Ceci crée une contradiction et donc, il ne peut pas exister de solutions.
Jusqu’à maintenant, les exemples qui fonctionnaient avaient pour \(1\) pour pgcd entre \(a\) et \(n\text{.}\) La proposition 3.3.8 ne permet pas de diviser dans une congruence sans changer la valeur du modulo. On considère par exemple \(6x\equiv 4\mod 10\text{.}\) On peut ajouter \(20\) à droite pour obtenir \(6x\equiv 24\mod 10\text{.}\) En divisant, on doit toutefois ajuster le modulo par un facteur \(\pgcd{(6,10)}=2\text{.}\) La nouvelle équation est donc équivalente à \(x\equiv 4\mod 5\text{.}\) On cherchait toutefois des solutions par rapport au modulo \(10\text{.}\) Peut-on ramener ces solutions dans ce cadre? Quels sont les nombres modulo \(10\) qui sont congrus à \(4\) modulo \(5\text{?}\) Il y a bien sûr \(4\text{,}\) mais aussi \(4+5=9\text{.}\) On peut donc dire qu’il y a “\(2\)” solutions (en réalité, une infinité, mais deux classes d’équivalence) à cette congruence. La proposition suivante donne le nombre de classes d’équivalence solutions à une congruence modulo \(n\text{.}\) Elle complète la proposition 3.3.15.
Soit \(a,b\in \mathbb{Z}\) et \(n\in \mathbb{N}\) avec \(a,n\) différents de \(0\text{.}\) Si \(\pgcd{(a,n)} \mid b\text{,}\) alors la congruence \(ax\equiv b\mod n\) possède des solutions, une infinité provenant d’autant de classes d’équivalence différente que la valeur du \(\pgcd{(a,n)}\text{.}\)
L’équation \(6x\equiv 4\mod 10\) qui avait pour solutions \(x\equiv 4\mod 10\) et \(x\equiv 9\mod 10\) vérifie bel et bien la proposition puisque les solutions proviennent de \(2=\pgcd{(6,10)}\) classes d’équivalence différentes modulo \(10\text{.}\) Un cas particulier découlant directement de la proposition précédente est celui où \(\pgcd{(a,n)}=1\text{.}\) Une solution à l’équation \(ax\equiv 1\mod n\) est alors appelée l’inverse de \(a\) modulo \(n\text{.}\)
Définition3.3.17.L’inverse d’un nombre modulo \(n\).
Soit \(a,n\) deux entiers avec \(\pgcd{(a,n)}=1\text{.}\) Les nombres dans l’unique classe d’équivalence satisfaisant l’équation \(ax\equiv 1\mod n\) sont appelés des inverses de \(a\) modulo \(n\text{.}\)
On considère l’équation \(3x\equiv 1 \mod 5\text{.}\) Puisque \(\pgcd{(3,5)}=1\text{,}\) il existe une classe d’équivalence pour laquelle le produit de tout nombre y appartenant multiplié par \(3\) donne \(1\text{.}\) Ce sont les inverses de \(3\) en modulo \(5\text{.}\) En regardant la table 3.3.13 ou tout simplement en essayant les quelques possibilités, on trouve que \(x=2\) est un inverse pour \(3\) en modulo \(5\text{.}\) C’est donc en fait toute la classe d’équivalence de \(2\) qui est considérée comme inverse.
Pour trouver un inverse, il faut trouver \(x\) tel que \(72\mid (5x-1)\text{.}\) En d’autres mots, \(5x-1=72y\) pour un certain \(y\in \mathbb{Z}\text{.}\) En réécrivant, on remarque qu’il faut que \(5x-72y=1\) et de plus, \(\pgcd{(5,72)}=1\text{.}\) Le lemme de Bézout et l’algorithme d’Euclide seront utiles pour trouver l’inverse. D’une part, on a
La transmission de messages secrets existe depuis toujours. Des messages entre amoureux aux codes secrets militaires, on a toujours cherché des moyens d’encoder de l’information afin de la transmettre pour que seul son destinataire puisse la déchiffrer. De nos jours, la majorité des opérations effectuées en ligne sont encryptées mathématiquement afin de les rendre sécuritaires: opérations bancaires, transactions par cartes de crédit, connexion à un compte quelconque, etc.
On illustre ici comment l’arithmétique modulaire peut aider à mettre en place un système d’encodage. La première de ces techniques est un peu primitive et est loin de celles utilisées de nos jours, car elle n’est pas assez sécuritaire, mais elles illustrent tout de même l’idée de la cryptographie.
L’un des premiers systèmes d’encodage est appelé le chiffrement de César. L’histoire veut que Jules César l’utilisait pour envoyer des messages à ses commandants. Il apparait toutefois évident que ce type de chiffrement était connu bien avant César. Son principe est simple, on associe à chaque lettre de l’alphabet un nombre correspondant à sa position, \(A=1,B=2,\ldots , Y=25,Z=26\text{.}\) On effectue par la suite un décalage uniforme des lettres du message à coder. Par exemple, le message “BONJOUR” est d’abord transformé en nombres, donnant \(2 15 14 10 15 21 18 \text{,}\) puis on décale l’alphabet en ajoutant à chaque nombre un paramètre de translation. Avec ce paramètre égal à \(3\text{,}\) on obtient \(5 18 17 13 18 24 21 \text{.}\) On reconvertit ensuite en lettres pour avoir le message crypté: “ERQMRXU”, qui est ensuite transmis au destinataire. Celui-ci pourra le décoder en effectuant la conversion en nombres et le décalage inverse s’il connait le paramètre de translation. L’arithmétique modulaire est utilisée pour faire l’encryption. Si la position d’une lettre additionnée du paramètre de translation dépasse \(26\text{,}\) on se ramène dans le bon intervalle en travaillant modulo \(26\text{.}\)
Les cellules Sage ci-dessous montrent comment on peut coder ce processus. La première cellule crée une fonction qui prend un message ne contenant que des caractères alphabétiques et le convertit en liste de nombres selon la position des lettres. On enlève les espaces et on met la phrase en majuscule.
La deuxième cellule crée une fonction qui, à partir d’une liste de nombres, renvoie un message. Ce message est écrit en majuscule et ne possède pas d’espaces.
La troisième cellule effectue le décalage d’une liste. À partir d’une liste L et d’un nombre \(n\text{,}\) on ajoute \(n\) à chaque entrée de la liste, en travaillant modulo \(26\text{.}\)
On teste finalement ici avec les messages secrets “Bonjour” et “Vive les maths”. Il faut s’assurer d’avoir exécuté toutes les cellules ci-dessus pour que la prochaine fonctionne.
Pour décoder un message crypté à l’aide de chiffrement de César, il suffit d’appliquer le chiffrement inverse. Ainsi, si on a le message “WPDPEFOTLYEDOPDTXDZYEWPDXPTWWPFCD” et qu’on sait que le message a été chiffré à l’aide d’un César avec paramètre \(11\text{,}\) on peut appliquer un chiffrement de \(-11\) pour décoder le message.
Le chiffrement de César est simple, mais peu sécuritaire. Avec un message suffisamment long, une personne pourrait intercepter le message et utiliser une analyse fréquentielle sur les lettres afin de deviner le paramètre de translation utilisé. Dans la langue française, la lettre “e” est la plus utilisée, avec un peu plus de \(12\%\) selon Wikipedia.
, on peut vérifier que la lettre la plus fréquente dans ce message est “L”. Sage peut être utile avec la fonction mode, qui retourne l’élément d’une liste qui apparait le plus souvent.
Il est donc plausible de penser que le chiffrement a envoyé “E” sur “L” et on peut tenter de déchiffrer ce message en appliquant un chiffrement inverse. Comme \(\text{E}=5\) et que \(\text{L}=12\text{,}\) on essaie un chiffrement de \(-7\text{.}\)
Pire encore, étant donné le petit nombre de possibilités, même sans avoir recours à l’analyse de la lettre la plus fréquente il est possible de déchiffrer le message. Il suffit d’essayer chacune des \(25\) possibilités (on n’a certainement pas fait un décalage de \(26\equiv 0 \mod 26\) caractères) et de constater que la plupart des messages seront insignifiants. On pourra alors rapidement décoder le bon message.
On imagine un instant que les systèmes précédents ne soient pas si facile que cela à décoder. Un autre désavantage de ces systèmes est que pour envoyer un message à quelqu’un, je dois aussi lui transmettre quelle encryption j’ai effectuée, afin qu’il puisse décrypter le message. Cette information doit être transmise de manière sécuritaire afin que personne d’autre que la personne visée par le message ne puisse le déchiffrer (encore une fois, on suppose que le décodage n’est pas facile). Un système où l’auteur et le destinataire doivent connaitre la méthode d’encryptage est appelé un système à clé privée.
L’un des systèmes d’encodage le plus populaire et sécuritaire est basé sur un concept simple. Il est facile de multiplier deux nombres, mais factoriser un nombre qui serait le produit de deux nombres (premiers) est difficile. Quand on dit difficile, on parle bien entendu de très grands nombres, contenant des centaines et des centaines de chiffres. Le système de chiffrement RSA utilise ce principe. Contrairement aux autres systèmes précédents, c’est un système à clé publique.
On suppose que Damien veut offrir aux gens la possibilité de lui envoyer des messages privés. Pour ce faire, il choisit deux nombres premiers. Pour l’exemple, il choisit \(p=7\) et \(q=13\text{.}\) Il garde ces deux nombres secrets, mais donne à qui veut bien lui envoyer un message le produit \(pq=91\text{.}\) Ensuite, Damien doit sélectionner un autre nombre \(e\) tel que \(\pgcd{(e,(p-1)(q-1))}=1\text{.}\) Puisque \((p-1)(q-1)=6\times 12=72\text{,}\) Damien choisit \(e=5\text{.}\) Damien donne aussi à qui veut bien lui envoyer un message ce nombre \(e\text{.}\) Ensemble, la paire \((91,5)\) constitue la clé publique de Damien.
Dans la réalité, Damien choisirait des nombres beaucoup plus grands, sans quoi la sécurité du système RSA expliqué ci-dessous serait nulle. On considère maintenant Marie, qui souhaite envoyer le message “Bonjour” à Damien. Marie commence par transformer son message en nombres et obtient 2 15 14 10 15 21 18 . Puis, elle prend chacun des chiffres \(M\) de son message et les encode à l’aide de la formule \(C=M^e\mod pq\text{.}\) Par exemple “B” devient \(2^5 \mod 91 =32\text{,}\) puis “O” devient \(15^5 \mod 91=71\text{,}\) “N” devient (reste) \(14\) et ainsi de suite. Le message devient ainsi 32 71 14 82 71 21 44. C’est ce message qui est transmis à Damien.
Damien reçoit donc le message 32 71 14 82 71 21 44 et entreprend donc de le décoder. Pour cela, il doit calculer un inverse de \(e\) modulo \((p-1)(q-1)\text{.}\) Puisque \(e\) avait été choisi pour qu’un inverse existe, il sait que c’est possible. Damien se souvient de l’exemple 3.3.18 et sait que \(d=29\) est un inverse pour \(5\) modulo \(72\text{.}\) Pour décoder le message de Marie, Damien applique à chaque nombre reçu la formule \(M=C^d \mod pq\text{.}\) On utilise Sage pour décoder le message.
La sécurité du système RSA vient du fait que, sans connaitre \(p\) et \(q\) individuellement, il est impossible de déterminer l’inverse de \(e\) et ainsi décoder le message. Lorsqu’en pratique, \(p,q,e\) sont choisis de sorte à posséder un très grands nombre de chiffres, même l’ordinateur le plus puissant ne pourra décoder le message en un temps raisonnable sans connaitre \(d\text{.}\)
L’explication du pourquoi le décodage fonctionne avec la formule \(M=C^d \mod pq\) utilise un résultat appelé le petit théorème de Fermat. On explore ceci dans l’exercice [provisional cross-reference: exo-RSA]. Les cellules suivantes permettent d’encoder un message avec le cryptage RSA à partir de deux nombres \(pq,e\) et d’en décoder un à partir des trois nombres \(p,q,e\text{.}\) Il faut s’assurer d’avoir exécuté les cellules plus haut afin d’utiliser certaines fonctions définies dans celles-ci.
Le principe RSA présenté ici est une simplification du vrai système RSA qui est encore utilisé. Dans la réalité, on va faire des blocs de lettres et juxtaposer leur équivalent en nombres avant de faire le cryptage.
Noter toute question qui demeure suite à la lecture de la section et la résolution des exercices ci-dessus ou toute précision/clarification à apporter. Note: cette question est facultative.
Ces exercices sont faits pour travailler en classe. Ils servent à approfondir les notions de la section et à atteindre les objectifs d’apprentissage plus avancés.
On considère les entiers naturels impairs \(I=\{1,3,5,7,9,\ldots\}\text{.}\) Pour \(n\in I\text{,}\) calculer \(n^2\mod 8\) pour quelques entiers. Comment démontrer que cela sera toujours vrai?
En calculant \(n^2\) pour les premières valeurs de \(n\in I\text{,}\) on obtient \(1^2=1\text{,}\)\(3^2=9\text{,}\)\(5^2=25\text{,}\)\(7^2=49\) et \(9^2=81\) . Ainsi, on remarque que \(1 \equiv 1^2 \equiv 3^2 \equiv 5^2 \equiv 7^2\equiv 9^2 \mod 8\text{.}\)
Pour pouvoir démontrer que \(n^2 \equiv 1 \mod 8\) pour tous les éléments de \(I\text{,}\) on remarque que \(n\) est impair si et seulement si \(n\) est congru à \(1\text{,}\)\(3\text{,}\)\(5\) ou \(7\) modulo \(8\text{.}\) Ainsi, si \(n\) est impair, en utilisant les propriétés 3.3.6, on obtient que \(n^2\) est congru à \(1^2\text{,}\)\(3^2\text{,}\)\(5^2\) ou \(7^2\) modulo \(8\text{.}\) Par les calculs précédents, on a alors que \(n^2\equiv 1 \mod 8\) pour tout \(n\in I\text{.}\)
Un tableau contenant une infinité de lignes et \(5\) colonnes contenant les nombres naturels est construit. Les premières lignes sont données à la table ci-dessous. On considère l’élément à la première ligne et la première colonne comme la position \((0,0)\text{.}\) De manière générale, un élément en position \((i,j)\) est à la ligne \(i\) et colonne \(j\text{.}\) Par exemple, \(15\) est à la position \((2,3)\text{.}\)
Clairement, si \(x=2\text{,}\) alors \(x\) est une solution de la première équation, mais pas de la deuxième. Cependant, on sait que toutes les solutions de la première équation s’écrivent comme \(x=2+3k\text{,}\) où \(k\in \Z\text{.}\)
Ainsi, on peut obtenir une solution en remplaçant cette fois \(k\) par \(2\) dans \(x=2+3k\text{,}\) ce qui donne \(x=2+3(2)=8\text{.}\) On peut en effet vérifier que:
En fait, on a montrer que, pour que \(x=2+3k\) soit une solution à la deuxième équation, on doit avoir \(k\in E_{2,5}\text{,}\) c’est-à-dire \(k=2+5k_1\text{,}\) pour \(k_1\in \Z\text{.}\)
Ainsi, en remplaçant dans \(x=2+3k\text{,}\) on a que \(x=2+3(2+5k_1)=8+15k_1\text{,}\) c’est-à-dire que \(x\) est une solution aux deux équations si et seulement si \(x\) est une solution à l’équation
Pour la congruence modulo \(n\text{,}\) on peut plus simplement écrire \((a,b) \leftrightarrow a\equiv b\mod n\text{.}\) Montrer que la congruence modulo est une relation d’équivalence.
On utilise principalement la version de congruence modulo \(n\) donnée par la proposition 3.3.5 On doit vérifier que la relation respecte les trois propriétés d’une relation d’équivalence.
Si \(a\equiv b \mod n\text{,}\) on doit montrer que \(b \equiv a \mod n\text{.}\) Or, si \(a\equiv b \mod n\text{,}\) on a que \(n \mid (a-b)\text{,}\) c’est-à-dire que \(nq=(a-b)\) pour un certain \(q\in \Z\text{.}\) On a alors \(n(-q)=(b-a)\text{,}\) d’où \(n\mid (b-a)\text{,}\) c’est-à-dire que \(b\equiv a \mod n\text{.}\)
Supposons que \(a\equiv b\mod n\) et \(b\equiv c\mod n\text{.}\) On a alors que \(n \mid (a-b)\) et \(n \mid (b-c)\text{.}\) Par définition de la divisibilité, on a \(nq_1=(a-b)\) et \(nq_2=(b-c)\text{,}\) pour certain \(q_1,\ q_2 \in \Z\text{.}\) En additionnant, on obtient
Qui a-t-il de particulier avec ces messages codés? Est-ce qu’il y a une lettre qui est facile à décoder? En utilisant des blocs de lettres comme dans le vrai RSA, ceci ne se produit pas.
Si même après avoir déterminé quelles lettres sont les plus fréquentes le message ne se déchiffre toujours pas, un indice avec décalage 5 a été crypté dans le titre de l’exercice.
Ne pas lire avant d’avoir réfléchi et cherché à propos de l’indice 1. L’indice ci-dessous est un décalage de César avec décalage \(21\text{.}\) Décoder chaque phrase individuellement pour une meilleure lisibilité.
Le message est un résumé du livre la disparition de George Perec, que l’on peut lire sur le site de Renaud-Bray. Ce livre a la particularité qu’il ne contient pas la lettre “e”, sauf pour le nom de l’auteur.
