Mathématiques pour l'informatique 201-N11 • Cégep à Montréal

Fiche de révision : l'arithmétique modulaire (201-N11)

Q: Le reste d'une division peut-il être négatif ?

Non, jamais en mathématiques : la division euclidienne impose un reste compris entre zéro et le module moins un. Moins dix-sept modulo cinq vaut donc trois, et non moins deux. L'opérateur pourcent des langages C, C plus plus et Java rend pourtant un reste négatif dans ce cas, contrairement à Python : c'est une convention de programmation, pas une définition.

Q: Peut-on simplifier une congruence par un facteur commun ?

Seulement si ce facteur est premier avec le module. Sinon, on divise aussi le module par le plus grand commun diviseur du facteur et du module. Par exemple quatre fois deux et quatre fois cinq sont congrus modulo six, alors que deux et cinq ne le sont pas : ils ne le deviennent que modulo trois.

Q: Comment calculer un inverse modulaire ?

On vérifie d'abord que le nombre est premier avec le module, sans quoi l'inverse n'existe pas. On déroule ensuite l'algorithme d'Euclide, puis on remonte les égalités pour écrire un égale a fois u plus n fois v. Le coefficient u est l'inverse, qu'on réduit entre zéro et le module moins un, puis qu'on vérifie par multiplication.

Q: Comment calculer une très grande puissance modulo n ?

On ne calcule jamais la puissance entière. Si le module est premier et ne divise pas la base, le petit théorème de Fermat permet de réduire l'exposant modulo le module moins un. On termine par l'exponentiation rapide, qui élève au carré et réduit à chaque étape, en environ deux fois le logarithme en base deux de l'exposant multiplications.

Q: Combien de solutions a une équation de congruence ?

Elle en a exactement autant que le plus grand commun diviseur du coefficient et du module, à condition que ce diviseur divise aussi le second membre; sinon elle n'en a aucune. On divise alors les deux membres et le module par ce diviseur, on résout, puis on déplie la solution obtenue en ajoutant le module réduit.

L'arithmétique modulaire n'est pas difficile à comprendre : c'est l'arithmétique de l'horloge. Elle est difficile à MANIPULER, parce que trois opérations sur quatre s'y comportent comme d'habitude et que la quatrième, la division, n'existe pas du tout.

Cette fiche est écrite pour les étudiants de cégep en techniques de l'informatique à Montréal et pour tous ceux qui abordent la cryptographie par les mathématiques. La série d'exercices corrigés du même chapitre met ensuite chaque réflexe à l'épreuve.

Le fil du chapitre

Travailler modulo $n$ , c'est remplacer un entier par son reste et calculer sur les restes. L'addition et la multiplication passent sans problème; la DIVISION ne passe jamais, et c'est de là que viennent presque toutes les pertes de points.

Ce chapitre fait partie de Mathématiques pour l'informatique, 201-N11

Avant ce chapitre

Cette fiche suppose ces notions acquises. Si une méthode ci-dessous reste opaque, c'est presque toujours l'une d'elles qui manque, pas la fiche.

Systèmes de numération informatique Fiche

Notions couvertes

Division euclidienne
Congruence
Arithmétique modulaire
Algorithme d'Euclide
Théorème de Bézout
Inverse modulaire
Diviseurs de zéro
Petit théorème de Fermat
Exponentiation rapide
Équation de congruence
Clé de contrôle
Chiffrement RSA

L'essentiel

Division euclidienne : le reste est TOUJOURS positif

• Pour $n>0$ , il existe un unique couple $(q\,;r)$ tel que $a=nq+r$ avec $0\leq r<n$ .
• Cela vaut aussi pour $a<0$ : $-17=5\times(-4)+3$ , donc $-17\bmod 5=3$ , et non $-2$ .
• L'opérateur $\%$ des langages C, C++ et Java ne suit PAS cette convention et rend un reste du signe du dividende. Python, lui, la suit.
• Le quotient se lit comme la partie entière PAR DÉFAUT de $\frac{a}{n}$ : $\left\lfloor\frac{-17}{5}\right\rfloor=-4$ , pas $-3$ .

La division euclidienne de

-17

par

5

donne

q=-4

r=3

, jamais

r=-2

: le reste se compte à partir du multiple situé À GAUCHE, donc il est toujours positif.

En examen, un reste négatif est une réponse fausse même quand la calculatrice l'affiche. Ajouter le module jusqu'à retomber dans $[0\,;n-1]$ coûte cinq secondes.

Congruences : ce qui passe, et ce qui ne passe pas

• $a\equiv b\pmod n$ signifie que $n$ divise $a-b$ , autrement dit que $a$ et $b$ ont le même reste.
• COMPATIBLE avec l'addition, la soustraction, la multiplication et donc les puissances : on réduit AVANT de calculer, jamais après.
• PAS compatible avec la division : $\frac{a}{b}\pmod n$ n'a aucun sens en général.
• SIMPLIFICATION : de $ac\equiv bc\pmod n$ on ne peut tirer $a\equiv b\pmod n$ que si $\mathrm{pgcd}(c,n)=1$ . Sinon il faut diviser le module par $\mathrm{pgcd}(c,n)$ .

Réduire avant de calculer est aussi ce qui rend les calculs faisables : $7^{50}\bmod 13$ se fait de tête en réduisant à chaque étape, et sature la calculatrice si l'on calcule $7^{50}$ d'abord.

Euclide, Bézout, inverse : la même machine à trois usages

• EUCLIDE : $\mathrm{pgcd}(a,n)=\mathrm{pgcd}(n,a\bmod n)$ , répété jusqu'à un reste nul. Le nombre d'étapes est majoré par environ cinq fois le nombre de chiffres.
• BÉZOUT : il existe $u$ et $v$ tels que $au+nv=\mathrm{pgcd}(a,n)$ , obtenus en remontant l'algorithme d'Euclide ÉTENDU.
• INVERSE : $a$ est inversible modulo $n$ si et seulement si $\mathrm{pgcd}(a,n)=1$ , et l'inverse est alors le $u$ de Bézout, réduit dans $[0\,;n-1]$ .
• Tous les éléments non nuls sont inversibles SI ET SEULEMENT SI $n$ est premier. Sinon apparaissent des DIVISEURS DE ZÉRO, comme $2\times 3\equiv 0\pmod 6$ .

L'algorithme d'Euclide pave le rectangle

48\times 18

par des carrés :

48=2\times 18+12

, puis

18=1\times 12+6

, puis

12=2\times 6

. Le côté du dernier carré est le PGCD, ici

6

Fermat, exponentiation rapide et équations de congruence

• FERMAT : si $p$ est PREMIER et ne divise pas $a$ , alors $a^{p-1}\equiv 1\pmod p$ .
• Conséquence pratique : on réduit la BASE modulo $p$ et l'EXPOSANT modulo $p-1$ . Deux modules différents, c'est le piège du chapitre.
• EXPONENTIATION RAPIDE : $a^{e}\bmod n$ en environ $2\log_{2}e$ multiplications, en élevant au carré et en réduisant à chaque étape.
• ÉQUATION $ax\equiv b\pmod n$ : elle admet des solutions si et seulement si $d=\mathrm{pgcd}(a,n)$ divise $b$ , et il y en a alors exactement $d$ modulo $n$ .

Sur un module non premier, c'est le théorème d'Euler qui remplace Fermat, avec $\varphi(n)$ à la place de $p-1$ . Appliquer Fermat tel quel à un module composé est faux.

Les pièges qui coûtent des points

Les erreurs ci-dessous sont celles que je corrige le plus souvent en séance. Chacune coûte des points sur une copie, même quand le raisonnement est juste.

1. Rendre un reste négatif

1 point à chaque occurrence, et un chiffrement faux dans un problème RSA

Ce qu'il ne faut pas écrire

« $-17\bmod 5=-2$ , c'est ce que ma calculatrice affiche. »

Ce qu'il faut écrire

« $-17=5\times(-4)+3$ , donc $-17\bmod 5=3$ : le reste d'une division euclidienne appartient toujours à $[0\,;n-1]$ . »

Pourquoi : L'opérateur $\%$ des langages de la famille C rend un reste du signe du dividende, ce qui n'est pas la définition mathématique. En Python et en mathématiques, le reste est positif.

2. Simplifier une congruence par un facteur non premier avec le module

toute la question

Ce qu'il ne faut pas écrire

« $4\times 2\equiv 4\times 5\pmod 6$ , donc $2\equiv 5\pmod 6$ . »

Ce qu'il faut écrire

« $\mathrm{pgcd}(4\,;6)=2\neq 1$ : on ne simplifie pas. On divise le MODULE par $2$ et l'on obtient $2\equiv 5\pmod 3$ , qui est vrai. »

Pourquoi : Modulo $6$ , $8$ et $20$ ont bien le même reste $2$ , alors que $2$ et $5$ ne sont pas congrus : la simplification perd de l'information dès que le facteur partage un diviseur avec le module.

3. Diviser dans une congruence

1 point ici, toute la question dès que le résultat n'est pas entier

Ce qu'il ne faut pas écrire

« $3x\equiv 6\pmod 7$ , donc $x\equiv\frac{6}{3}=2$ . »

Ce qu'il faut écrire

« On MULTIPLIE par l'inverse de $3$ modulo $7$ , qui est $5$ puisque $3\times 5=15\equiv 1$ : $x\equiv 5\times 6=30\equiv 2\pmod 7$ . »

Pourquoi : La division n'existe pas modulo $n$ . Le raccourci fonctionne par hasard quand le quotient tombe juste, et il s'effondre dès que ce n'est pas le cas : $3x\equiv 5\pmod 7$ n'a rien à voir avec $\frac{5}{3}$ .

4. Réduire l'exposant modulo $p$ au lieu de $p-1$

toute la question

Ce qu'il ne faut pas écrire

« $3^{100}\bmod 7$ : je réduis $100$ modulo $7$ , ce qui donne $2$ , donc $3^{2}=9\equiv 2$ . »

Ce qu'il faut écrire

« La base se réduit modulo $7$ , l'EXPOSANT modulo $7-1=6$ . Comme $100=6\times 16+4$ , on a $3^{100}\equiv 3^{4}=81\equiv 4\pmod 7$ . »

Les puissances

3^{k}\bmod 7

reprennent à l'identique tous les SIX pas, et

6=7-1

: c'est le petit théorème de Fermat. L'exposant se réduit donc modulo

p-1

, la base modulo

p

Pourquoi : Le petit théorème de Fermat dit $a^{p-1}\equiv 1$ , donc c'est la période $p-1$ qui gouverne l'exposant. Deux modules cohabitent dans le même calcul, et les confondre donne un résultat plausible et faux.

5. Croire que tout élément non nul est inversible

toute la question, et un calcul qui ne peut pas aboutir

Ce qu'il ne faut pas écrire

« Modulo $6$ , je cherche l'inverse de $2$ pour résoudre $2x\equiv 4$ . »

Ce qu'il faut écrire

« $\mathrm{pgcd}(2\,;6)=2\neq 1$ : $2$ n'est PAS inversible modulo $6$ . C'est même un diviseur de zéro, puisque $2\times 3\equiv 0\pmod 6$ . »

Pourquoi : L'inversibilité modulo $n$ est exactement la primalité avec $n$ . Sur un module composé, une partie des éléments n'a pas d'inverse, et l'équation se résout alors par la condition de Bézout, pas par un inverse.

6. Appliquer Fermat sans vérifier ses deux hypothèses

toute la question, et une conclusion fausse en cryptographie

Ce qu'il ne faut pas écrire

« $a^{n-1}\equiv 1\pmod n$ pour tout $a$ et tout $n$ . »

Ce qu'il faut écrire

« Le théorème demande $n$ PREMIER et $n$ ne divisant pas $a$ . Modulo $6$ , qui n'est pas premier, $2^{5}=32\equiv 2$ et non $1$ . »

Pourquoi : Sur un module composé, c'est le théorème d'Euler qui s'applique, avec $\varphi(n)$ à la place de $p-1$ . Utiliser Fermat hors de son cadre donne un résultat qui ressemble à une réponse.

7. Calculer la puissance entière avant de réduire

le temps de l'épreuve, et une calculatrice qui sature

Ce qu'il ne faut pas écrire

« $7^{50}\bmod 13$ : je calcule $7^{50}$ , puis je divise par $13$ . »

Ce qu'il faut écrire

« Je réduis à CHAQUE étape : $7^{2}=49\equiv 10$ , $7^{4}\equiv 10^{2}=100\equiv 9$ , et ainsi de suite par élévations au carré successives. »

Pourquoi : $7^{50}$ a plus de quarante chiffres : aucune calculatrice d'examen ne le rend exactement, et l'arrondi rend le reste faux. La compatibilité de la congruence avec la multiplication existe précisément pour éviter cela.

8. Annoncer une seule solution à une équation de congruence

la moitié des points de la question

Ce qu'il ne faut pas écrire

« $14x\equiv 30\pmod{100}$ : je trouve $x\equiv 45$ , c'est la solution. »

Ce qu'il faut écrire

« $d=\mathrm{pgcd}(14\,;100)=2$ divise $30$ , donc il y a exactement DEUX solutions modulo $100$ : $x\equiv 45$ et $x\equiv 95$ . »

Pourquoi : Le nombre de solutions modulo $n$ vaut $d=\mathrm{pgcd}(a,n)$ dès que $d$ divise $b$ . Résoudre l'équation réduite donne une solution modulo $\frac{n}{d}$ , qu'il faut ensuite déplier en $d$ solutions modulo $n$ .

Quelle méthode choisir

Ce qu'on a le droit de faire dans une congruence

Avant chaque manipulation, on regarde de quelle opération il s'agit. Trois sont libres, une est interdite, deux sont conditionnelles.

Si addition, soustraction, multiplication → libre : on réduit chaque terme AVANT de calculer

Exemple : $17\times 23\equiv 2\times 3=6\pmod 5$
Si élévation à une puissance, module quelconque → libre sur la BASE, en réduisant à chaque carré; l'exposant, lui, ne se réduit pas sans hypothèse

Exemple : $7^{4}\equiv 10^{2}\equiv 9\pmod{13}$
Si réduction de l'EXPOSANT, module premier $p$ ne divisant pas $a$ → autorisée modulo $p-1$ , par le petit théorème de Fermat

Exemple : $3^{100}\equiv 3^{4}\equiv 4\pmod 7$

Sur un module composé, remplacer $p-1$ par $\varphi(n)$ et vérifier que $\mathrm{pgcd}(a,n)=1$ .
Si simplification d'un facteur commun $c$ → autorisée seulement si $\mathrm{pgcd}(c,n)=1$ ; sinon diviser AUSSI le module par $\mathrm{pgcd}(c,n)$

Exemple : $4\times 2\equiv 4\times 5\pmod 6$ donne $2\equiv 5\pmod 3$
Si division → INTERDITE. On multiplie par l'inverse, qui n'existe que si $\mathrm{pgcd}(a,n)=1$

Exemple : $3x\equiv 6\pmod 7$ se résout par $\times 5$ , pas par $\div 3$

Quand l'inverse n'existe pas, l'équation n'est pas forcément insoluble : elle a $\mathrm{pgcd}(a,n)$ solutions dès que ce PGCD divise le second membre. C'est le cas le plus fréquent en examen.

Quel outil selon ce que l'énoncé demande

Les questions du chapitre se ramènent à six formes, et chacune a un outil unique. On l'identifie avant d'écrire la première ligne.

Si « quel est le reste de », « quel jour de la semaine » → division euclidienne, puis réduction du calcul modulo $n$

Exemple : $2^{1000}\bmod 7$ par la périodicité
Si « calculer $\mathrm{pgcd}(a,b)$ » → algorithme d'Euclide, en tableau de restes successifs

Exemple : $\mathrm{pgcd}(48\,;18)=6$ en trois divisions
Si « trouver $u$ et $v$ tels que $au+nv=d$ » → algorithme d'Euclide ÉTENDU, en remontant les égalités

Exemple : $50-7\times 7=1$ donne $u=-7$
Si « l'inverse de $a$ modulo $n$ » → vérifier $\mathrm{pgcd}(a,n)=1$ , puis Bézout : l'inverse est $u$ réduit dans $[0\,;n-1]$

Exemple : l'inverse de $7$ modulo $50$ est $-7\equiv 43$
Si « résoudre $ax\equiv b\pmod n$ » → calculer $d=\mathrm{pgcd}(a,n)$ ; si $d\nmid b$ , aucune solution; sinon diviser tout par $d$ , inverser, puis déplier en $d$ solutions

Exemple : $14x\equiv 30\pmod{100}$ donne $x\equiv 45$ et $x\equiv 95$
Si « un exposant énorme » → Fermat pour réduire l'exposant, puis exponentiation rapide pour finir

Exemple : $3^{100}\bmod 7$ se ramène à $3^{4}$

Toutes ces questions commencent par le même geste : calculer un PGCD. C'est lui qui décide si l'inverse existe, combien de solutions l'équation possède, et si Fermat s'applique.

La rédaction attendue

Le correcteur coche des étapes. Les voici dans l'ordre, avec la phrase de conclusion qu'il attend mot pour mot.

Calculer un inverse modulaire par Euclide étendu

Quand l'utiliser : L'énoncé demande l'inverse de $a$ modulo $n$ , ou une résolution qui en dépend.

1 Vérifier l'existence AVANT de calculer : « $\mathrm{pgcd}(7\,;50)=1$ , donc $7$ est inversible modulo $50$ . »
2 Dérouler l'algorithme d'Euclide en écrivant chaque division : « $50=7\times 7+1$ , puis $7=1\times 7+0$ . »
3 Remonter pour isoler le PGCD : « $1=50-7\times 7$ . »
4 Lire l'identité de Bézout modulo $n$ : « donc $-7\times 7\equiv 1\pmod{50}$ . »
5 Réduire le coefficient dans $[0\,;n-1]$ et VÉRIFIER : « $-7\equiv 43$ , et $7\times 43=301=6\times 50+1$ . »

Phrase de conclusion

L'inverse de $7$ modulo $50$ est $43$ , puisque $7\times 43=301\equiv 1\pmod{50}$ .

Le piège : Rendre un coefficient de Bézout négatif comme inverse. Il est juste, mais un inverse s'écrit dans $[0\,;n-1]$ , et la vérification finale par multiplication est le seul moyen de s'assurer qu'on n'a pas inversé $u$ et $v$ .

Barème : En général 1 point pour la vérification du PGCD, 1 point pour l'algorithme déroulé, 1 point pour la remontée, 1 point pour l'inverse réduit et vérifié.

Résoudre une équation de congruence $ax\equiv b\pmod n$

Quand l'utiliser : Toute équation linéaire modulo $n$ , y compris déguisée en problème de clé de contrôle ou de calendrier.

1 Calculer $d=\mathrm{pgcd}(a,n)$ et TRANCHER : « $d=2$ divise $30$ , donc il y a des solutions, exactement $2$ modulo $100$ . »
2 Diviser les trois quantités par $d$ , le module compris : « $7x\equiv 15\pmod{50}$ . »
3 Calculer l'inverse de $\frac{a}{d}$ modulo $\frac{n}{d}$ par Euclide étendu.
4 Multiplier et réduire : « $x\equiv 43\times 15\equiv 45\pmod{50}$ . »
5 DÉPLIER les $d$ solutions modulo $n$ en ajoutant $\frac{n}{d}$ , puis vérifier chacune dans l'équation de départ.

Phrase de conclusion

L'équation $14x\equiv 30\pmod{100}$ admet exactement deux solutions, $x\equiv 45\pmod{100}$ et $x\equiv 95\pmod{100}$ .

Le piège : Oublier de diviser le MODULE en même temps que les deux membres. On obtient alors $7x\equiv 15\pmod{100}$ , dont la solution ne vérifie pas l'équation de départ.

Barème : 1 point pour la condition d'existence, 1 point pour la division par $d$ module compris, 1 point pour l'inverse, 1 point pour le dépliage des $d$ solutions.

Vérifier avant de rendre

Cinq minutes de vérification récupèrent plus de points qu'un exercice de plus commencé à la hâte.

Vérifier que le reste est dans $[0\,;n-1]$

Relire chaque reste écrit sur la copie : un nombre négatif ou supérieur ou égal au module est une faute, quelle que soit la calculatrice qui l'a produit.

Un $-2$ modulo $5$ se corrige en ajoutant $5$ , ce qui donne $3$ . Un $7$ modulo $5$ se corrige en retranchant $5$ , ce qui donne $2$ .
Vérifier un inverse en multipliant

Multiplier $a$ par l'inverse trouvé et réduire : le résultat doit valoir exactement $1$ . C'est immédiat et cela attrape toutes les erreurs de la remontée de Bézout.

$7\times 43=301=6\times 50+1$ : correct. Si l'on avait rendu $-7$ sans le réduire, la vérification passerait aussi, mais l'écriture serait refusée.
Vérifier Bézout en recalculant la combinaison

Reporter $u$ et $v$ dans $au+nv$ et comparer au PGCD annoncé. Une erreur de signe se voit immédiatement, et c'est l'erreur la plus fréquente de la remontée.

$7\times(-7)+50\times 1=-49+50=1$ : conforme au PGCD. Un résultat de $99$ signalerait que $u$ et $v$ ont été échangés.
Vérifier une puissance par la périodicité

Calculer les premières puissances de la base et repérer le rang où l'on retombe sur $1$ . Ce rang divise $p-1$ et permet de recalculer le résultat autrement.

Les puissances de $3$ modulo $7$ donnent $3$ , $2$ , $6$ , $4$ , $5$ puis $1$ : la période est $6$ , donc $3^{100}=3^{96}\times 3^{4}\equiv 3^{4}\equiv 4$ .

L'exercice type décortiqué

Résoudre $14x\equiv 30\pmod{100}$ , jusqu'aux deux solutions

Résoudre dans $\mathbb{Z}$ l'équation de congruence $14x\equiv 30\pmod{100}$ .

On précisera le nombre exact de solutions modulo $100$ et l'on vérifiera chacune.

Étape 1

$\mathrm{pgcd}(14\,;100)$ : $100=7\times 14+2$ , puis $14=7\times 2+0$ , donc $d=2$ . Comme $2$ divise $30$ , l'équation a des solutions, et il y en a exactement $d=2$ modulo $100$ .

Pourquoi

Cette première ligne décide de tout : elle dit s'il y a des solutions et combien. Une copie qui la saute peut trouver la bonne valeur et perdre quand même la moitié des points, faute d'avoir compté.

Étape 2

On divise les DEUX membres et le MODULE par $d=2$ : $7x\equiv 15\pmod{50}$ .

Pourquoi

Le module se divise lui aussi, sans quoi l'équation obtenue n'est pas équivalente. C'est l'oubli qui produit une solution ne vérifiant pas l'énoncé de départ.

Étape 3

$\mathrm{pgcd}(7\,;50)=1$ , donc $7$ est inversible modulo $50$ . Euclide : $50=7\times 7+1$ , donc $1=50-7\times 7$ et $-7\times 7\equiv 1\pmod{50}$ .

Pourquoi

On vérifie l'inversibilité avant de chercher l'inverse. Après la division par $d$ , elle est garantie, mais l'écrire vaut le point de rigueur et prouve que la condition a été comprise.

Étape 4

L'inverse de $7$ modulo $50$ est donc $-7\equiv 43$ . Contrôle : $7\times 43=301=6\times 50+1$ .

Pourquoi

On réduit dans $[0\,;49]$ et l'on vérifie par multiplication. Ces deux gestes prennent dix secondes et éliminent la totalité des erreurs de signe de la remontée.

Étape 5

On multiplie l'équation par $43$ : $x\equiv 43\times 15=645\pmod{50}$ , et $645=12\times 50+45$ , donc $x\equiv 45\pmod{50}$ .

Pourquoi

On multiplie, on ne divise jamais. Le résultat est ici une congruence modulo $50$ , pas modulo $100$ : la question n'est pas encore terminée, et c'est le moment où la moitié des copies s'arrête.

Étape 6

On déplie modulo $100$ : $x\equiv 45$ et $x\equiv 45+50=95$ . Ce sont bien $d=2$ solutions, comme annoncé à la première ligne.

Pourquoi

Le dépliage consiste à ajouter $\frac{n}{d}$ autant de fois que nécessaire. Le compte annoncé au début sert ici de contrôle : deux solutions attendues, deux solutions obtenues.

Étape 7

Vérification : $14\times 45=630=6\times 100+30$ et $14\times 95=1330=13\times 100+30$ . Les deux valeurs conviennent.

Pourquoi

On réinjecte chaque solution dans l'équation de DÉPART, pas dans l'équation réduite. C'est la seule vérification qui attrape l'oubli de la division du module.

Conclusion rédigée

L'équation $14x\equiv 30\pmod{100}$ admet exactement deux solutions modulo $100$ : $x\equiv 45$ et $x\equiv 95$ .

L'erreur classique sur cet exercice : Diviser seulement les deux membres et garder le module : $7x\equiv 15\pmod{100}$ . L'inverse de $7$ modulo $100$ vaut $43$ également, et l'on obtient $x\equiv 45\pmod{100}$ , donc une seule solution au lieu de deux. La vérification sur l'équation de départ ne révèle rien, puisque $45$ convient : seule la condition sur le PGCD signale la solution manquante.

À savoir par cœur

• Le reste d'une division euclidienne est TOUJOURS dans $[0\,;n-1]$ , même pour un dividende négatif.
• On réduit AVANT de calculer : la congruence passe l'addition et la multiplication, jamais la division.
• $ac\equiv bc\pmod n$ donne $a\equiv b$ seulement si $\mathrm{pgcd}(c,n)=1$ ; sinon on divise aussi le module.
• $a$ est inversible modulo $n$ si et seulement si $\mathrm{pgcd}(a,n)=1$ , et l'inverse est le $u$ de Bézout.
• Tous les non nuls sont inversibles si et seulement si $n$ est PREMIER; sinon il y a des diviseurs de zéro.
• Fermat : $p$ premier et $p\nmid a$ donnent $a^{p-1}\equiv 1\pmod p$ . Base modulo $p$ , EXPOSANT modulo $p-1$ .
• $ax\equiv b\pmod n$ a des solutions si et seulement si $\mathrm{pgcd}(a,n)$ divise $b$ , et il y en a alors exactement $\mathrm{pgcd}(a,n)$ .
• Tout commence par un PGCD : il décide de l'inverse, du nombre de solutions et de l'usage de Fermat.

Questions fréquentes

Le reste d'une division peut-il être négatif ?

Non, jamais en mathématiques : la division euclidienne impose un reste compris entre zéro et le module moins un. Moins dix-sept modulo cinq vaut donc trois, et non moins deux. L'opérateur pourcent des langages C, C plus plus et Java rend pourtant un reste négatif dans ce cas, contrairement à Python : c'est une convention de programmation, pas une définition.

Peut-on simplifier une congruence par un facteur commun ?

Seulement si ce facteur est premier avec le module. Sinon, on divise aussi le module par le plus grand commun diviseur du facteur et du module. Par exemple quatre fois deux et quatre fois cinq sont congrus modulo six, alors que deux et cinq ne le sont pas : ils ne le deviennent que modulo trois.

Comment calculer un inverse modulaire ?

On vérifie d'abord que le nombre est premier avec le module, sans quoi l'inverse n'existe pas. On déroule ensuite l'algorithme d'Euclide, puis on remonte les égalités pour écrire un égale a fois u plus n fois v. Le coefficient u est l'inverse, qu'on réduit entre zéro et le module moins un, puis qu'on vérifie par multiplication.

Comment calculer une très grande puissance modulo n ?

On ne calcule jamais la puissance entière. Si le module est premier et ne divise pas la base, le petit théorème de Fermat permet de réduire l'exposant modulo le module moins un. On termine par l'exponentiation rapide, qui élève au carré et réduit à chaque étape, en environ deux fois le logarithme en base deux de l'exposant multiplications.

Combien de solutions a une équation de congruence ?

Elle en a exactement autant que le plus grand commun diviseur du coefficient et du module, à condition que ce diviseur divise aussi le second membre; sinon elle n'en a aucune. On divise alors les deux membres et le module par ce diviseur, on résout, puis on déplie la solution obtenue en ajoutant le module réduit.

Passer à la pratique

Exercices corrigés : L'arithmétique modulaire

Une méthode se prouve sur une copie, pas sur une fiche. La série du même chapitre reprend chacun de ces pièges dans un exercice, avec le corrigé rédigé étape par étape.

10 exercices corrigés
100 points
150 minutes

Faire les exercices

Fiche précédente Systèmes de numération informatique Fiche suivante Théorie des ensembles et relations

Voir aussi

Toutes les fiches Tous les exercices Systèmes de numération (201-N11)Ensembles et relations (201-N11)Récurrence et récursivité (201-N11)Examen de synthèse (201-N11)Maths et informatique au cégep Tutorat cégep

Vous cherchez un tuteur en mathématiques pour l'informatique 201-N11 à Montréal ?

Contactez-moi pour une première séance. On travaille l'arithmétique modulaire au niveau réel des évaluations, des congruences jusqu'à l'algorithme d'Euclide étendu et à RSA.

Me contacter WhatsApp

Site par Studio Squalli

Fiche de révision : l'arithmétique modulaire (201-N11)

L'essentiel

Division euclidienne : le reste est TOUJOURS positif

Congruences : ce qui passe, et ce qui ne passe pas

Euclide, Bézout, inverse : la même machine à trois usages

Fermat, exponentiation rapide et équations de congruence

Les pièges qui coûtent des points

1. Rendre un reste négatif

2. Simplifier une congruence par un facteur non premier avec le module

3. Diviser dans une congruence

4. Réduire l'exposant modulo ppp au lieu de p−1p-1p−1

5. Croire que tout élément non nul est inversible

6. Appliquer Fermat sans vérifier ses deux hypothèses

7. Calculer la puissance entière avant de réduire

8. Annoncer une seule solution à une équation de congruence

Quelle méthode choisir

Ce qu'on a le droit de faire dans une congruence

Quel outil selon ce que l'énoncé demande

La rédaction attendue

Calculer un inverse modulaire par Euclide étendu

Résoudre une équation de congruence ax≡b(modn)ax\equiv b\pmod nax≡b(modn)

Vérifier avant de rendre

L'exercice type décortiqué

Résoudre 14x≡30(mod100)14x\equiv 30\pmod{100}14x≡30(mod100), jusqu'aux deux solutions

À savoir par cœur

Questions fréquentes

Le reste d'une division peut-il être négatif ?

Peut-on simplifier une congruence par un facteur commun ?

Comment calculer un inverse modulaire ?

Comment calculer une très grande puissance modulo n ?

Combien de solutions a une équation de congruence ?

Exercices corrigés : L'arithmétique modulaire

Voir aussi

Vous cherchez un tuteur en mathématiques pour l'informatique 201-N11 à Montréal ?

4. Réduire l'exposant modulo $p$ au lieu de $p-1$

Résoudre une équation de congruence $ax\equiv b\pmod n$

Résoudre $14x\equiv 30\pmod{100}$ , jusqu'aux deux solutions