Exercice 0.1 : Réduire modulo n : dix calculs directs

Pour chaque ligne, donnez le reste $r$ demandé, avec $0\leq r<n$ , ou le PGCD à la dernière ligne. La calculatrice ne sert à rien : tous les nombres se réduisent à la main.

Une seule méthode : réduire AVANT de calculer. On remplace chaque nombre par son reste, terme par terme dans une somme, facteur par facteur dans un produit ; pour une puissance, on cherche le premier exposant qui ramène à $1$ , par le cycle des puissances ou par le petit théorème de Fermat quand le module est premier, puis on réduit l'exposant. Un reste négatif n'existe pas : on ajoute $n$ jusqu'à tomber dans $[0\,;n[$ .

a) $347\bmod 9$ .
b) $-38\bmod 7$ .
c) $(482+937+615)\bmod 8$ , en réduisant chaque terme.
d) $(123\times 456)\bmod 11$ , en réduisant chaque facteur.
e) Le reste de $n^{3}+2n$ modulo $4$ , sachant que $n\equiv 3\pmod 4$ .
f) $2\,999^{2}\bmod 11$ .
g) $4^{41}\bmod 9$ , par le cycle des puissances de $4$ .
h) Le dernier chiffre de $7^{83}$ , c'est-à-dire $7^{83}\bmod 10$ .
i) $2^{405}\bmod 13$ , par le petit théorème de Fermat.
j) Le PGCD de $1\,518$ et de $391$ , par l'algorithme d'Euclide.

Voir la correction

Réponses

a) $347=9\times 38+5$ ; $5$
b) $-38=7\times(-6)+4$ ; $4$
c) $2+1+7\equiv 2$ ; $2$
d) $2\times 5=10$ ; $10$
e) $27+6=33\equiv 1$ ; $1$
f) $7^{2}=49\equiv 5$ ; $5$
g) $4^{3}\equiv 1$ , $4^{41}\equiv 4^{2}$ ; $7$
h) cycle de longueur $4$ , $7^{83}\equiv 7^{3}$ ; $3$
i) $2^{12}\equiv 1$ , $2^{405}\equiv 2^{9}$ ; $5$
j) dernier reste non nul ; $23$

Le geste qui décide de tout : réduire avant de multiplier ou d'élever à une puissance. La congruence est compatible avec la somme, le produit et donc la puissance : on a le droit de remplacer chaque nombre par son reste à toute étape, et l'on n'a JAMAIS à écrire $2\,999^{2}$ ni $2^{405}$ .

a)

$347=9\times 38+5$ , donc $347\bmod 9=5$ . Vérification : $9\times 38=342$ et $342+5=347$ .

b)

Il faut un quotient qui laisse un reste dans $[0\,;7[$ : $-38=7\times(-6)+4$ , donc $-38\bmod 7=4$ . Piège : $-38=7\times(-5)-3$ donne $-3$ , qui n'est pas un reste ; on ajoute $7$ et l'on retrouve $4$ .

c)

$482=8\times 60+2$ , $937=8\times 117+1$ et $615=8\times 76+7$ . La somme est donc congrue à $2+1+7=10\equiv 2\pmod 8$ . Vérification : $482+937+615=2\,034=8\times 254+2$ .

d)

$123=11\times 11+2$ et $456=11\times 41+5$ , donc $123\times 456\equiv 2\times 5=10\pmod{11}$ . Le reste vaut $10$ , sans avoir calculé $56\,088$ .

e)

On remplace $n$ par son reste $3$ : $3^{3}+2\times 3=27+6=33=4\times 8+1$ , donc le reste vaut $1$ , quel que soit l'entier $n\equiv 3\pmod 4$ . Contrôle sur $n=7$ : $343+14=357=4\times 89+1$ .

f)

$2\,999=11\times 272+7$ , donc $2\,999^{2}\equiv 7^{2}=49=44+5\equiv 5\pmod{11}$ . Piège : élever d'abord au carré, ce qui oblige à diviser $8\,994\,001$ par $11$ .

g)

Le cycle : $4^{1}\equiv 4$ , $4^{2}=16\equiv 7$ , $4^{3}\equiv 4\times 7=28\equiv 1\pmod 9$ . Il a pour longueur $3$ , et $41=3\times 13+2$ , donc $4^{41}=\left(4^{3}\right)^{13}\times 4^{2}\equiv 1\times 7=7\pmod 9$ . Piège : réduire l'exposant modulo $9$ , le module, au lieu de la longueur du cycle.

h)

Le cycle modulo $10$ : $7$ , $49\equiv 9$ , $9\times 7=63\equiv 3$ , $3\times 7=21\equiv 1$ , de longueur $4$ . Comme $83=4\times 20+3$ , $7^{83}\equiv 7^{3}\equiv 3\pmod{10}$ : le dernier chiffre est $3$ .

i)

$13$ est premier et ne divise pas $2$ , donc $2^{12}\equiv 1\pmod{13}$ . Or $405=12\times 33+9$ , donc $2^{405}\equiv 2^{9}=512=13\times 39+5\equiv 5\pmod{13}$ . Piège : réduire l'exposant modulo $13$ au lieu de $13-1=12$ , ce qui donne $405\equiv 2$ et un faux $4$ .

j)

$1\,518=3\times 391+345$ ; $391=1\times 345+46$ ; $345=7\times 46+23$ ; $46=2\times 23+0$ . Le dernier reste non nul est $23$ , donc le PGCD vaut $23$ . Contrôle : $1\,518=23\times 66$ et $391=23\times 17$ .

Contrôle : un reste se vérifie en recalculant $nq+r$ , et il doit tomber dans $[0\,;n[$ ; un cycle de puissances se vérifie en constatant qu'il revient bien sur $1$ avant de s'en servir pour réduire l'exposant.

Coche ici les exercices faits ou à revoir : un compte gratuit, sans mot de passe, retient tes coches et tes réponses justes d'une visite à l'autre, te dit quel chapitre attaquer ensuite et te permet de demander l'exercice qui te manque. Crée ton espace, un courriel suffit.

Exercice 0.2 : Inverser et résoudre modulo n : huit calculs directs

Pour chaque ligne, donnez l'inverse, la solution ou le nombre demandé. Un inverse et une solution s'écrivent comme un reste, entre $0$ et $n-1$ .

Une seule méthode : calculer d'abord $\mathrm{pgcd}(a,n)$ , sans quoi on ne sait pas si l'inverse existe ; trouver ensuite l'inverse par l'algorithme d'Euclide étendu, ou par essais quand $n$ est petit ; enfin, pour résoudre $ax\equiv b\pmod n$ , multiplier les deux membres par l'inverse de $a$ . Si $d=\mathrm{pgcd}(a,n)>1$ , l'équation n'a de solution que si $d$ divise $b$ : on divise alors tout par $d$ , module compris, et l'on obtient $d$ solutions modulo $n$ .

a) L'inverse de $5$ modulo $11$ .
b) L'inverse de $4$ modulo $15$ .
c) L'inverse de $9$ modulo $24$ existe-t-il ?
d) L'inverse de $23$ modulo $60$ , par l'algorithme d'Euclide étendu.
e) Les coefficients de Bézout $u$ et $v$ tels que $75u+32v=1$ , avec $0<u<32$ .
f) La solution de $5x\equiv 3\pmod{17}$ .
g) La solution de $7x\equiv 5\pmod{18}$ .
h) L'équation $8x\equiv 12\pmod{28}$ : le nombre de solutions modulo $28$ , puis la plus petite solution positive.

Tape tes réponses, la page te dit juste ou faux 0/10

a)

Inverse

b)

Inverse

c)

L'inverse existe-t-il ?

d)

Inverse

e)

u

v

f)

Solution

x

g)

Solution

x

h)

Nombre de solutions

Plus petite solution positive

Voir la correction

Réponses

a) $5\times 9\equiv 1\pmod{11}$ ; $9$
b) $4\times 4\equiv 1\pmod{15}$ ; $4$
c) $\mathrm{pgcd}(9,24)=3$ ; non
d) $1=5\times 60-13\times 23$ ; $47$
e) $1=3\times 75-7\times 32$ ; $u=3$ , $v=-7$
f) $x\equiv 7\times 3$ ; $x=4$
g) $x\equiv 13\times 5$ ; $x=11$
h) $2x\equiv 3\pmod 7$ ; $4$ solutions, la plus petite $5$

Le geste qui décide de tout : le PGCD AVANT tout calcul. $\mathrm{pgcd}(a,n)=1$ dit que l'inverse existe et que l'équation a une seule solution modulo $n$ ; sinon, l'inverse n'existe pas, et l'équation a plusieurs solutions ou aucune.

a)

$\mathrm{pgcd}(5,11)=1$ . Par essais : $5\times 9=45=44+1\equiv 1\pmod{11}$ , donc l'inverse vaut $9$ . Piège : répondre $\frac{1}{5}$ ou $0{,}2$ ; un inverse modulaire est un ENTIER entre $0$ et $10$ .

b)

$\mathrm{pgcd}(4,15)=1$ , et $4\times 4=16=15+1\equiv 1\pmod{15}$ : $4$ est son propre inverse modulo $15$ .

c)

Non : $\mathrm{pgcd}(9,24)=3\neq 1$ . Tous les multiples de $9$ sont des multiples de $3$ , et leurs restes modulo $24$ aussi, donc aucun ne vaut $1$ . Piège : croire que tout nombre non nul plus petit que le module est inversible ; ce n'est vrai que si le module est premier.

d)

Euclide : $60=2\times 23+14$ ; $23=1\times 14+9$ ; $14=1\times 9+5$ ; $9=1\times 5+4$ ; $5=1\times 4+1$ . Remontée : $1=5-4=5-(9-5)=2\times 5-9=2(14-9)-9=2\times 14-3\times 9=2\times 14-3(23-14)=5\times 14-3\times 23=5(60-2\times 23)-3\times 23=5\times 60-13\times 23$ . Donc $-13\times 23\equiv 1\pmod{60}$ , et l'inverse vaut $-13+60=47$ . Vérification : $23\times 47=1\,081=18\times 60+1$ . Piège : s'arrêter sur $-13$ , qui n'est pas écrit comme un reste.

e)

Euclide : $75=2\times 32+11$ ; $32=2\times 11+10$ ; $11=1\times 10+1$ . Remontée : $1=11-10=11-(32-2\times 11)=3\times 11-32=3(75-2\times 32)-32=3\times 75-7\times 32$ . Donc $u=3$ et $v=-7$ , et $u$ est bien entre $0$ et $32$ . Vérification : $225-224=1$ . Piège : développer tous les produits à chaque étape, ce qui fait perdre la trace de $75$ et de $32$ ; on substitue une division à la fois, de bas en haut.

f)

$17$ est premier, donc l'inverse de $5$ existe : $5\times 7=35=34+1$ , c'est $7$ . On multiplie les deux membres par $7$ : $x\equiv 7\times 3=21\equiv 4\pmod{17}$ . Vérification : $5\times 4=20=17+3$ .

g)

$\mathrm{pgcd}(7,18)=1$ , et $7\times 13=91=5\times 18+1$ , donc l'inverse de $7$ modulo $18$ vaut $13$ . Alors $x\equiv 13\times 5=65=3\times 18+11\equiv 11\pmod{18}$ . Vérification : $7\times 11=77=4\times 18+5$ . Piège : chercher à diviser $5$ par $7$ ; modulo $18$ , on ne divise jamais, on multiplie par l'inverse.

h)

$d=\mathrm{pgcd}(8,28)=4$ , et $4$ divise $12$ : il y a $4$ solutions modulo $28$ . On divise tout par $4$ , module compris : $2x\equiv 3\pmod 7$ . L'inverse de $2$ modulo $7$ est $4$ , donc $x\equiv 12\equiv 5\pmod 7$ . Modulo $28$ , les solutions sont $5$ , $12$ , $19$ et $26$ , et la plus petite vaut $5$ . Vérification : $8\times 5=40=28+12$ . Piège : diviser $8$ et $12$ par $4$ en gardant le module $28$ , ce qui donne $2x\equiv 3\pmod{28}$ , sans solution puisque $2x-3$ est impair.

Contrôle : un inverse $u$ de $a$ se vérifie en calculant $au\bmod n$ , qui doit valoir $1$ ; une solution se vérifie en la remplaçant dans l'équation ; des coefficients de Bézout, en recalculant $au+bv$ . Chaque vérification coûte une multiplication et une division.

Exercice 1 : La division euclidienne et le reste

Toute l'arithmétique modulaire tient dans une opération que l'on croit connaître depuis l'école primaire. Le fil de la série : on ne s'intéresse plus au QUOTIENT mais au RESTE, et un reste est toujours positif, même quand le dividende ne l'est pas.

a) Énoncez le théorème de la division euclidienne de $a$ par $n$ , en précisant l'encadrement du reste.
b) Calculez le quotient et le reste de la division de 2026 par 12, puis de 2026 par 7.
c) Calculez $-17 \bmod 5$ et $-1 \bmod 12$ . Attention au signe du reste.
d) En Python, l'opérateur $\%$ renvoie toujours un reste du signe du DIVISEUR ; en C et en Java, il renvoie un reste du signe du DIVIDENDE. Que valent $-17\ \%\ 5$ dans chaque langage ?
e) Si aujourd'hui est un mardi, quel jour sera-t-il dans 100 jours ? Et il y a 100 jours ?

Tape tes réponses, la page te dit juste ou faux 0/13

a)

L'encadrement du reste est

Le couple

(q,r)

est

b)

Quotient de 2026 par 12

Reste de 2026 par 12

Quotient de 2026 par 7

Reste de 2026 par 7

c)

-17 \bmod 5

-1 \bmod 12

d)

En Python

En C et en Java

e)

100 \bmod 7

Dans 100 jours

Il y a 100 jours

Voir la correction

Réponses

a) $a = nq+r$ avec $0 \le r < n$ , le couple $(q,r)$ étant unique
b) $2026 = 12(168)+10$ et $2026 = 7(289)+3$
c) $-17 \bmod 5 = 3$ et $-1 \bmod 12 = 11$
d) $3$ en Python, $-2$ en C et en Java
e) Jeudi dans 100 jours, dimanche il y a 100 jours

a)

Pour tout entier $a$ et tout entier $n>0$ , il existe un UNIQUE couple d'entiers $(q,r)$ tel que $a=nq+r$ avec $0\leq r<n$ . Deux choses comptent dans cet énoncé : l'existence et l'unicité d'une part, et surtout l'ENCADREMENT du reste entre 0 inclus et $n$ exclu. C'est cet encadrement qui interdit un reste négatif, et c'est lui qu'on oublie quand $a<0$ .

b)

$2026=12\times 168+10$ , donc $q=168$ et $r=10$ : c'est ce que montre l'horloge de la figure, où l'on tourne 168 fois avant de s'arrêter sur 10. Pour 7 : $2026=7\times 289+3$ , donc $q=289$ et $r=3$ . On vérifie toujours en recalculant $nq+r$ , ce qui coûte une seconde et attrape toutes les erreurs de table.

c)

Pour $-17$ par 5 : le quotient doit être choisi de sorte que le reste tombe dans $[0;5[$ . Avec $q=-4$ : $-17=5\times(-4)+3$ , donc $r=3$ . Le réflexe $-17=5\times(-3)-2$ donnerait $r=-2$ , qui n'est pas un reste valide. Pour $-1$ par 12 : $-1=12\times(-1)+11$ , donc $r=11$ : c'est le dernier cran de l'horloge avant de repasser par zéro, ce qui est exactement l'image à retenir.

d)

En PYTHON, $-17\ \%\ 5$ vaut 3, la convention mathématique, puisque le diviseur 5 est positif. En C et en JAVA, l'opérateur renvoie $-2$ , du signe du dividende. Les deux langages calculent correctement, ils ne répondent simplement pas à la même question. Conséquence pratique pour un programmeur : un code d'indexation circulaire écrit en C doit corriger le cas négatif, par exemple avec $((a\ \%\ n)+n)\ \%\ n$ , alors que le même code en Python fonctionne tel quel.

e)

Les jours de la semaine se comptent modulo 7. $100=7\times 14+2$ , donc dans 100 jours on avance de 2 crans : mardi plus 2 donne JEUDI. Il y a 100 jours, on recule de 2 crans : mardi moins 2 donne DIMANCHE. On peut aussi écrire $-100\bmod 7=5$ et avancer de 5, ce qui donne également dimanche, puisque avancer de 5 ou reculer de 2 revient au même sur un cycle de 7.

Exercice 2 : Les congruences et leurs règles de calcul

Écrire $a\equiv b\pmod n$ n'est pas une notation décorative : c'est une relation d'ÉQUIVALENCE compatible avec l'addition et la multiplication, ce qui permet de calculer sur les restes comme sur les nombres.

a) Donnez la définition de $a\equiv b\pmod n$ en termes de divisibilité, puis en termes de restes.
b) Démontrez que la congruence modulo $n$ est réflexive, symétrique et transitive.
c) Démontrez que si $a\equiv b$ et $c\equiv d$ modulo $n$ , alors $a+c\equiv b+d$ et $ac\equiv bd$ .
d) Calculez le reste de $17^{4}$ modulo 5 sans jamais élever 17 à la puissance 4.
e) La compatibilité vaut-elle pour la DIVISION ? Testez sur $6\equiv 12\pmod 6$ divisé par 2.

Tape tes réponses, la page te dit juste ou faux 0/13

a)

En termes de divisibilité

En termes de restes

b)

La transitivité vient de ce que

La congruence modulo

n

est donc

c)

L'astuce de la démonstration du produit consiste à

d)

17 \bmod 5

2^{4} \bmod 5

Reste de

17^{4}

modulo 5

La règle est

e)

La division est-elle compatible ?

3 \bmod 6

6 \bmod 6

On peut simplifier par

k

si

Voir la correction

Réponses

a) $n$ divise $a-b$ , ce qui revient à dire que $a$ et $b$ ont le même reste modulo $n$
b) Réflexive, symétrique et transitive : c'est une relation d'équivalence, à $n$ classes
c) $(a+c)-(b+d) = (k+\ell)n$ et $ac-bd = (ck+b\ell)n$ , en ajoutant et retranchant $bc$
d) $17 \equiv 2$ , donc $17^{4} \equiv 2^{4} = 16 \equiv 1 \pmod 5$
e) NON : $6 \equiv 12 \pmod 6$ , mais $3 \not\equiv 6 \pmod 6$ . On simplifie par $k$ seulement si $k$ est premier avec $n$

a)

DIVISIBILITÉ : $a\equiv b\pmod n$ signifie que $n$ divise $a-b$ . RESTES : cela signifie que $a$ et $b$ ont le MÊME reste dans la division par $n$ . Les deux formulations sont équivalentes, et il faut savoir passer de l'une à l'autre : la première sert dans les démonstrations, la seconde dans les calculs.

b)

RÉFLEXIVE : $n$ divise $a-a=0$ , donc $a\equiv a$ . SYMÉTRIQUE : si $n$ divise $a-b$ , il divise aussi $b-a=-(a-b)$ , donc $b\equiv a$ . TRANSITIVE : si $n$ divise $a-b$ et $b-c$ , il divise leur somme $(a-b)+(b-c)=a-c$ , donc $a\equiv c$ . Les trois propriétés font de la congruence une relation d'équivalence, dont les classes sont exactement les $n$ ensembles de nombres ayant le même reste.

c)

Par hypothèse $a-b=kn$ et $c-d=\ell n$ pour deux entiers $k$ et $\ell$ . SOMME : $(a+c)-(b+d)=(a-b)+(c-d)=(k+\ell)n$ , multiple de $n$ ✓. PRODUIT : $ac-bd=ac-bc+bc-bd=c(a-b)+b(c-d)=(ck+b\ell)n$ , multiple de $n$ ✓. L'astuce du produit consiste à ajouter et retrancher $bc$ , ce qui fait apparaître les deux hypothèses ; elle vaut la peine d'être retenue, elle resservira ailleurs.

d)

$17\equiv 2\pmod 5$ , car $17=5\times 3+2$ . La compatibilité avec le produit permet d'élever les deux membres à la puissance 4 : $17^{4}\equiv 2^{4}=16\equiv 1\pmod 5$ . Le reste vaut donc 1, alors que $17^{4}=83\,521$ , un nombre qu'on n'a jamais eu à écrire. C'est tout l'intérêt du calcul modulaire : on réduit AVANT de multiplier, jamais après.

e)

NON, la division n'est pas compatible en général. On a bien $6\equiv 12\pmod 6$ , puisque $12-6=6$ . En divisant les deux membres par 2 : $3\equiv 6\pmod 6$ serait faux, car $6-3=3$ n'est pas un multiple de 6. La règle correcte est qu'on peut simplifier par $k$ à condition de diviser AUSSI le modulo par $\mathrm{pgcd}(k,n)$ , ou bien si $k$ est premier avec $n$ . C'est cette restriction qui rend l'exercice 5 sur les inverses nécessaire.

Exercice 3 : Calculer dans les entiers modulo n

L'ensemble des restes modulo $n$ est un monde clos où l'on additionne et multiplie sans jamais sortir. Sa table de multiplication révèle une différence profonde selon que $n$ est premier ou non.

a) Dressez la table d'addition modulo 5. Chaque ligne contient-elle chaque élément exactement une fois ?
b) La figure donne la table de multiplication modulo 7, privée du zéro. Vérifiez trois cases au hasard et dites ce que l'on observe sur chaque ligne.
c) Dressez la table de multiplication modulo 6, privée du zéro. Que constate-t-on de différent ?
d) Trouvez deux éléments non nuls dont le produit est nul modulo 6. Comment appelle-t-on de tels éléments, et pourquoi n'en existe-t-il pas modulo 7 ?
e) Énoncez la règle générale qui distingue les deux cas.

Tape tes réponses, la page te dit juste ou faux 0/15

a)

Chaque ligne contient chaque élément

La raison est qu'ajouter un nombre fixé est

b)

3 \times 5 \bmod 7

4 \times 6 \bmod 7

2 \times 4 \bmod 7

Chaque ligne contient

c)

La ligne de 2 modulo 6 donne

La ligne de 3 donne

Lignes qui contiennent 1

d)

Premier facteur

Second facteur

On les appelle

Modulo 7 c'est impossible parce que

e)

a

est inversible modulo

n

si et seulement si

Tous les éléments non nuls sont inversibles si et seulement si

Voir la correction

Réponses

a) Oui : ajouter un nombre fixé est une permutation, pour tout $n$
b) $3\times5 \equiv 1$ , $4\times6 \equiv 3$ , $2\times4 \equiv 1$ : chaque ligne contient 1, donc tout élément non nul est inversible
c) La ligne de 2 vaut $2,4,0,2,4$ et celle de 3 vaut $3,0,3,0,3$ : des zéros, et pas de 1
d) $2 \times 3 = 6 \equiv 0 \pmod 6$ : des DIVISEURS DE ZÉRO, impossibles modulo 7 qui est premier
e) $a$ est inversible modulo $n$ si et seulement si $\mathrm{pgcd}(a,n)=1$ ; tous le sont si et seulement si $n$ est premier

a)

La table d'addition modulo 5 s'obtient en additionnant puis en prenant le reste. Sa première ligne, celle de 0, est $0,1,2,3,4$ ; celle de 1 est $1,2,3,4,0$ ; celle de 2 est $2,3,4,0,1$ , et ainsi de suite. OUI, chaque ligne contient chaque élément exactement une fois : ajouter un nombre fixé est une permutation, car on peut toujours revenir en arrière en ajoutant l'opposé. C'est vrai pour tout $n$ , premier ou non.

b)

Vérifications : $3\times 5=15=14+1\equiv 1$ ; $4\times 6=24=21+3\equiv 3$ ; $2\times 4=8\equiv 1$ . On observe que CHAQUE LIGNE contient chaque élément non nul exactement une fois, et en particulier qu'elle contient 1. Autrement dit, tout élément non nul possède un INVERSE modulo 7, ce qui n'a rien d'évident et sera le sujet de l'exercice 5.

c)

Modulo 6, la ligne de 2 donne $2,4,0,2,4$ pour les multiplicateurs $1,2,3,4,5$ : elle contient un ZÉRO alors qu'aucun des deux facteurs n'est nul, et elle ne contient PAS 1. La ligne de 3 donne $3,0,3,0,3$ , encore pire. Seules les lignes de 1 et de 5 contiennent 1. La table est donc très différente de celle modulo 7.

d)

$2\times 3=6\equiv 0\pmod 6$ , avec $2\neq 0$ et $3\neq 0$ . On appelle de tels éléments des DIVISEURS DE ZÉRO. Ils apparaissent parce que 6 se factorise en $2\times 3$ : le produit récupère tous les facteurs de 6 et devient un multiple de 6. Modulo 7 c'est impossible, car 7 est PREMIER : si 7 divise un produit $ab$ , il divise $a$ ou $b$ , propriété qui définit précisément les nombres premiers.

e)

Un élément $a$ est inversible modulo $n$ si et seulement si $\mathrm{pgcd}(a,n)=1$ . Par conséquent, TOUS les éléments non nuls sont inversibles si et seulement si $n$ est PREMIER, auquel cas les entiers modulo $n$ forment un corps. Si $n$ est composé, les éléments qui partagent un facteur avec $n$ ne sont pas inversibles et sont des diviseurs de zéro. Cette distinction est ce qui rend les modules premiers si précieux en cryptographie et en codes correcteurs.

Exercice 4 : Le PGCD et l'algorithme d'Euclide

L'algorithme le plus ancien encore en usage date de 300 avant notre ère et il est toujours celui que les processeurs exécutent. Sa justification tient en une ligne de congruence.

def pgcd(a, n):
    while n != 0:
        a, n = n, a % n
    return a

def pgcd_rec(a, n):
    if n == 0:
        return a
    return pgcd_rec(n, a % n)

a) Démontrez que $\mathrm{pgcd}(a,n)=\mathrm{pgcd}(n,a\bmod n)$ , ce qui justifie l'algorithme.
b) Déroulez l'algorithme d'Euclide sur 1071 et 462, comme sur la figure, et donnez le PGCD.
c) Déroulez-le sur 240 et 46.
d) Écrivez l'algorithme en Python, en version itérative puis en version récursive.
e) Combien d'étapes l'algorithme demande-t-il au maximum ? Quel couple de nombres constitue le pire cas ?

Tape tes réponses, la page te dit juste ou faux 0/15

a)

Si

d

divise

a

et

n

, alors il divise

Les deux couples ont donc

b)

Premier reste

Deuxième reste

Troisième reste

PGCD

c)

Premier reste

Deuxième reste

Troisième reste

Quatrième reste

PGCD

d)

La version itérative remplace

(a,n)

par

Le cas de base de la version récursive est

e)

Le nombre d'étapes est au plus environ

Le pire cas est

Voir la correction

Réponses

a) $d$ divise $a$ et $n$ si et seulement si il divise $n$ et $r$ : mêmes diviseurs communs, même PGCD
b) $147$ , puis $21$ , puis $0$ : $\mathrm{pgcd}(1071,462) = 21$
c) $10, 6, 4, 2, 0$ : $\mathrm{pgcd}(240,46) = 2$ , en cinq étapes contre trois
d) Itérative : $(a,n) \to (n, a \bmod n)$ . Récursive : même égalité, cas de base $n=0$
e) Au plus environ 5 fois le nombre de chiffres du plus petit ; pire cas, deux Fibonacci consécutifs

a)

Posons $r=a\bmod n$ , donc $a=nq+r$ . Si $d$ divise $a$ et $n$ , alors il divise $a-nq=r$ , donc il divise $n$ et $r$ . Réciproquement, si $d$ divise $n$ et $r$ , il divise $nq+r=a$ , donc il divise $a$ et $n$ . Les deux couples ont donc EXACTEMENT les mêmes diviseurs communs, et en particulier le même plus grand. L'algorithme consiste alors à remplacer le couple par un couple plus petit jusqu'à ce que le reste s'annule.

b)

$1071=2\times 462+147$ ; $462=3\times 147+21$ ; $147=7\times 21+0$ . Le dernier reste non nul est 21, donc $\mathrm{pgcd}(1071,462)=21$ . La figure donne la lecture géométrique : on pave le rectangle par des carrés de plus en plus petits, et le côté du dernier carré est le PGCD. Trois divisions ont suffi là où la recherche des diviseurs de 1071 en aurait demandé beaucoup plus.

c)

$240=5\times 46+10$ ; $46=4\times 10+6$ ; $10=1\times 6+4$ ; $6=1\times 4+2$ ; $4=2\times 2+0$ . Le PGCD vaut 2. Notez que ces deux nombres, plus petits que ceux de la question b, ont demandé PLUS d'étapes : le nombre d'étapes ne dépend pas de la taille des nombres mais de la suite des quotients, tous égaux à 1 dans le pire cas.

d)

Les deux versions tiennent en quatre lignes et se lisent directement sur la question a. La version ITÉRATIVE remplace le couple $(a,n)$ par $(n,a\bmod n)$ à chaque tour et s'arrête quand le second terme s'annule ; c'est alors le premier qui porte le PGCD. La version RÉCURSIVE traduit la même égalité mot pour mot, avec le cas de base $n=0$ qui renvoie $a$ . La récursive est plus lisible et son nombre d'appels est le nombre de divisions, donc elle ne risque aucun débordement de pile pour des entiers de taille raisonnable ; l'itérative évite malgré tout ce risque et reste la forme employée dans les bibliothèques.

e)

Le théorème de Lamé affirme que le nombre d'étapes est au plus environ $5$ fois le nombre de CHIFFRES du plus petit des deux nombres, ce qui est remarquablement peu : moins de 50 étapes pour des nombres de dix chiffres. Le PIRE CAS est celui de deux nombres de FIBONACCI consécutifs, comme 89 et 55, pour lesquels tous les quotients valent 1 et où l'algorithme ne peut donc rien accélérer. C'est un exemple rare où le pire cas d'un algorithme est connu explicitement.

Exercice 5 : L'inverse modulaire et les équations de congruence

On ne divise pas modulo $n$ : on multiplie par un inverse, quand il existe. Savoir décider s'il existe, puis le calculer, est la compétence centrale du chapitre.

a) Donnez la condition d'existence de l'inverse de $a$ modulo $n$ , et trouvez l'inverse de 3 modulo 7 par recherche exhaustive.
b) Trouvez l'inverse de 4 modulo 9, puis montrez que 4 n'a pas d'inverse modulo 8.
c) Résolvez $3x\equiv 2\pmod 7$ .
d) Résolvez $4x\equiv 6\pmod{10}$ . Combien de solutions y a-t-il modulo 10 ?
e) Résolvez $6x\equiv 4\pmod{9}$ , ou montrez qu'il n'y a pas de solution.

Tape tes réponses, la page te dit juste ou faux 0/15

a)

L'inverse existe si et seulement si

Inverse de 3 modulo 7

b)

Inverse de 4 modulo 9

pgcd(4, 8)

Les multiples de 4 modulo 8 valent

c)

Inverse de 3 modulo 7

Solution

x

modulo 7

Nombre de solutions modulo 7

d)

pgcd(4, 10)

Première solution

Seconde solution

Nombre de solutions modulo 10

e)

pgcd(6, 9)

Nombre de solutions

La raison est que

Voir la correction

Réponses

a) L'inverse existe si et seulement si $\mathrm{pgcd}(a,n)=1$ ; celui de 3 modulo 7 vaut 5
b) $4^{-1} = 7$ modulo 9 ; modulo 8, $\mathrm{pgcd}(4,8)=4$ , donc aucun inverse
c) $x \equiv 3 \pmod 7$ , solution unique
d) $x = 4$ et $x = 9$ : deux solutions modulo 10, autant que le PGCD
e) Aucune solution : $\mathrm{pgcd}(6,9)=3$ ne divise pas 4

a)

L'inverse de $a$ modulo $n$ existe si et seulement si $\mathrm{pgcd}(a,n)=1$ , c'est-à-dire si $a$ et $n$ sont PREMIERS ENTRE EUX. Pour 3 modulo 7 : $\mathrm{pgcd}(3,7)=1$ , l'inverse existe. On essaie : $3\times 1=3$ , $3\times 2=6$ , $3\times 3=9\equiv 2$ , $3\times 4=12\equiv 5$ , $3\times 5=15\equiv 1$ ✓. L'inverse de 3 modulo 7 est donc 5.

b)

$\mathrm{pgcd}(4,9)=1$ , l'inverse existe : $4\times 7=28=27+1\equiv 1\pmod 9$ , donc l'inverse est 7. Modulo 8, en revanche, $\mathrm{pgcd}(4,8)=4\neq 1$ : il n'y a pas d'inverse. On le vérifie sur la table, les multiples de 4 modulo 8 ne prennent que les valeurs 0 et 4, jamais 1. Le même nombre 4 est donc inversible ou non selon le module, ce qui montre bien que l'inversibilité est une propriété du COUPLE et non du nombre.

c)

On multiplie les deux membres par l'inverse de 3, c'est-à-dire par 5 : $5\times 3x\equiv 5\times 2$ , soit $15x\equiv 10$ , soit $x\equiv 3\pmod 7$ puisque $15\equiv 1$ et $10\equiv 3$ . Vérification : $3\times 3=9\equiv 2\pmod 7$ ✓. Il y a donc exactement UNE solution modulo 7, comme toujours lorsque le coefficient est inversible.

d)

$\mathrm{pgcd}(4,10)=2$ , qui ne vaut pas 1 : on ne peut pas inverser. Mais 2 DIVISE le second membre 6, donc l'équation a des solutions. On divise tout par 2, MODULE COMPRIS : $2x\equiv 3\pmod 5$ . Cette fois $\mathrm{pgcd}(2,5)=1$ et l'inverse de 2 modulo 5 est 3, d'où $x\equiv 3\times 3=9\equiv 4\pmod 5$ . Modulo 10, cela donne DEUX solutions, $x=4$ et $x=9$ . Vérification : $4\times 4=16\equiv 6$ ✓ et $4\times 9=36\equiv 6$ ✓. Le nombre de solutions est égal au PGCD, ici 2.

e)

$\mathrm{pgcd}(6,9)=3$ , et 3 NE DIVISE PAS 4. L'équation n'a donc AUCUNE solution. On le voit directement : $6x$ est toujours un multiple de 3, donc son reste modulo 9 appartient à $\{0,3,6\}$ , et 4 n'y figure pas. Règle générale : $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)$ modulo $n$ .

Exercice 6 : Bézout et l'algorithme d'Euclide étendu

L'algorithme d'Euclide donne le PGCD ; en gardant la trace des calculs, il donne bien plus : deux coefficients qui expriment ce PGCD comme combinaison des deux nombres de départ. C'est ce qui rend le calcul d'un inverse rapide.

def euclide_etendu(a, b):
    r, u, v = a, 1, 0
    rp, up, vp = b, 0, 1
    while rp != 0:
        q = r // rp
        r, u, v, rp, up, vp = rp, up, vp, r - q*rp, u - q*up, v - q*vp
    return r, u, v

def inverse(a, n):
    d, u, _ = euclide_etendu(a, n)
    if d != 1:
        return None
    return u % n

a) Énoncez le théorème de Bézout et dites ce qu'il devient lorsque les deux nombres sont premiers entre eux.
b) Trouvez deux entiers $u$ et $v$ tels que $1071u+462v=21$ , en remontant les divisions de l'exercice 4.
c) Calculez l'inverse de 17 modulo 43 par l'algorithme d'Euclide étendu.
d) Comparez le coût de cette méthode avec celui de la recherche exhaustive de l'exercice 5.
e) Écrivez l'algorithme d'Euclide étendu en Python.

Tape tes réponses, la page te dit juste ou faux 0/13

a)

Il existe

u

et

v

tels que

Quand les deux nombres sont premiers entre eux, cela devient

b)

u

v

Vérification

c)

Premier reste

Deuxième reste

Troisième reste

Inverse de 17 modulo 43

Vérification

17 \times 38 \bmod 43

d)

La recherche exhaustive coûte

L'algorithme d'Euclide étendu coûte

e)

L'algorithme renvoie

Voir la correction

Réponses

a) $au+bv = \mathrm{pgcd}(a,b)$ , qui devient $au+bv=1$ pour deux nombres premiers entre eux
b) $u = -3$ et $v = 7$ : $-3(1071)+7(462) = 21$
c) $1 = 2(43)-5(17)$ , donc l'inverse de 17 modulo 43 vaut $-5 \equiv 38$
d) Exhaustive : de l'ordre de $n$ , exponentiel. Euclide étendu : linéaire en le nombre de chiffres
e) L'algorithme renvoie le triplet PGCD, $u$ , $v$ , en propageant les coefficients à chaque tour

a)

Pour tous entiers $a$ et $b$ non tous nuls, il existe des entiers $u$ et $v$ tels que $au+bv=\mathrm{pgcd}(a,b)$ . Lorsque $a$ et $b$ sont PREMIERS ENTRE EUX, cela devient $au+bv=1$ , et réciproquement : une telle écriture prouve que le PGCD vaut 1, puisque tout diviseur commun divise le membre de gauche donc divise 1. C'est le critère le plus commode pour démontrer que deux nombres sont premiers entre eux.

b)

On remonte les divisions. De $462=3\times 147+21$ on tire $21=462-3\times 147$ . De $1071=2\times 462+147$ on tire $147=1071-2\times 462$ . En substituant : $21=462-3\left(1071-2\times 462\right)=462-3\times 1071+6\times 462=7\times 462-3\times 1071$ . Donc $u=-3$ et $v=7$ . Vérification : $-3\times 1071+7\times 462=-3213+3234=21$ ✓. La discipline est de substituer UNE division à la fois, de bas en haut, sans jamais développer les produits avant la fin.

c)

Euclide d'abord : $43=2\times 17+9$ ; $17=1\times 9+8$ ; $9=1\times 8+1$ ; $8=8\times 1+0$ . Le PGCD vaut 1, l'inverse existe. Remontée : $1=9-8$ ; puis $8=17-9$ donne $1=9-(17-9)=2\times 9-17$ ; puis $9=43-2\times 17$ donne $1=2\left(43-2\times 17\right)-17=2\times 43-5\times 17$ . Donc $-5\times 17\equiv 1\pmod{43}$ , et l'inverse de 17 est $-5$ , c'est-à-dire $38$ modulo 43. Vérification : $17\times 38=646=43\times 15+1$ ✓.

d)

La recherche exhaustive teste les valeurs $1,2,\dots,n-1$ jusqu'à tomber sur 1 : son coût est de l'ordre de $n$ multiplications, donc EXPONENTIEL en le nombre de chiffres de $n$ . L'algorithme d'Euclide étendu, lui, effectue au plus environ $5$ fois le nombre de chiffres de divisions, donc un coût LINÉAIRE en ce nombre. Sur un module de 600 chiffres comme ceux du chiffrement RSA, la première méthode est impossible dans l'âge de l'Univers et la seconde prend une fraction de milliseconde. C'est cet écart qui rend la cryptographie moderne praticable.

e)

Le code ci-dessous renvoie le triplet formé du PGCD et des deux coefficients de Bézout, en propageant les coefficients à chaque tour de boucle.

Exercice 7 : Le petit théorème de Fermat et l'exponentiation rapide

Calculer $3^{100}$ puis prendre le reste est impossible à la main et coûteux pour une machine. Deux idées ramènent le calcul à quelques lignes : un théorème qui raccourcit l'exposant, un algorithme qui le décompose en binaire.

def puissance_mod(a, e, n):
    resultat = 1
    a = a % n
    while e > 0:
        if e % 2 == 1:
            resultat = (resultat * a) % n
        a = (a * a) % n
        e = e // 2
    return resultat

a) Énoncez le petit théorème de Fermat et vérifiez-le sur $a=3$ et $p=7$ en dressant le cycle des puissances, comme sur la figure.
b) Calculez le reste de $3^{100}$ modulo 7.
c) Calculez le reste de $2^{1000}$ modulo 11.
d) Calculez $7^{11}$ modulo 13 par exponentiation rapide, en décomposant l'exposant en binaire, puis vérifiez le résultat par le théorème de Fermat.
e) Combien de multiplications l'exponentiation rapide demande-t-elle pour un exposant de 600 chiffres, contre la méthode naïve ?

Tape tes réponses, la page te dit juste ou faux 0/14

a)

Si

p

est premier et ne divise pas

a

, alors

3^{6} \bmod 7

Longueur du cycle

b)

100 \bmod 6

Reste de

3^{100}

modulo 7

c)

2^{10} \bmod 11

Reste de

2^{1000}

modulo 11

d)

7^{2} \bmod 13

7^{4} \bmod 13

7^{8} \bmod 13

7^{11} \bmod 13

Inverse de 7 modulo 13

e)

Multiplications de l'exponentiation rapide

La méthode naïve en demanderait

Voir la correction

Réponses

a) $a^{p-1} \equiv 1 \pmod p$ ; le cycle de 3 modulo 7 est $3,2,6,4,5,1$ , de longueur 6
b) $100 \equiv 4 \pmod 6$ , donc $3^{100} \equiv 3^{4} = 81 \equiv 4 \pmod 7$
c) $2^{10} \equiv 1$ , donc $2^{1000} \equiv 1 \pmod{11}$
d) $7^{11} \equiv 2 \pmod{13}$ , confirmé par Fermat : $7^{11} \equiv 7^{-1} = 2$
e) Environ 3986 multiplications contre $10^{600}$

a)

Si $p$ est PREMIER et si $p$ ne divise pas $a$ , alors $a^{p-1}\equiv 1\pmod p$ . Vérification avec $a=3$ et $p=7$ : $3^{1}=3$ , $3^{2}=9\equiv 2$ , $3^{3}\equiv 6$ , $3^{4}\equiv 18\equiv 4$ , $3^{5}\equiv 12\equiv 5$ , $3^{6}\equiv 15\equiv 1$ ✓. La figure montre ce cycle de longueur 6 : les six valeurs non nulles apparaissent toutes, exactement une fois, avant que le cycle ne se referme sur 1.

b)

Le théorème permet de réduire l'EXPOSANT modulo $p-1=6$ . Comme $100=6\times 16+4$ , on a $3^{100}=\left(3^{6}\right)^{16}\times 3^{4}\equiv 1^{16}\times 3^{4}=81\equiv 4\pmod 7$ . Le reste vaut 4. Retenez la règle et sa limite : on réduit la BASE modulo $p$ , et l'EXPOSANT modulo $p-1$ , jamais l'inverse.

c)

$p=11$ est premier et ne divise pas 2, donc $2^{10}\equiv 1\pmod{11}$ . Comme $1000=10\times 100$ , on a $2^{1000}=\left(2^{10}\right)^{100}\equiv 1^{100}=1\pmod{11}$ . Le reste vaut 1. Un nombre de plus de trois cents chiffres a été réduit en une ligne.

d)

$11$ s'écrit $1011$ en binaire, donc $7^{11}=7^{8}\times 7^{2}\times 7^{1}$ . On calcule les carrés successifs modulo 13 : $7^{1}\equiv 7$ ; $7^{2}=49\equiv 10$ ; $7^{4}\equiv 10^{2}=100\equiv 9$ ; $7^{8}\equiv 9^{2}=81\equiv 3$ . Produit : $3\times 10\times 7=210\equiv 210-208=2\pmod{13}$ . VÉRIFICATION par Fermat : $7^{12}\equiv 1$ , donc $7^{11}\equiv 7^{-1}$ , l'inverse de 7 modulo 13. Or $7\times 2=14\equiv 1$ , donc cet inverse vaut 2 ✓. Deux chemins indépendants, même réponse.

e)

La méthode naïve demande $N-1$ multiplications pour $a^{N}$ , soit environ $10^{600}$ opérations pour un exposant de 600 chiffres : c'est inconcevable, l'Univers n'a connu qu'environ $10^{17}$ secondes. L'exponentiation rapide en demande au plus $2\log_{2}N$ , soit environ $2\times 600\times 3{,}3219\approx 3986$ multiplications, l'affaire de quelques millisecondes. C'est cette différence, et elle seule, qui permet à un navigateur d'ouvrir une connexion chiffrée en un clin d'œil.

Exercice 8 : Cinq affirmations à corriger

Chacune des cinq affirmations suivantes est FAUSSE. Dites pourquoi et donnez l'énoncé correct.

1) « $-17 \bmod 5$ vaut $-2$ , puisque $-17=5\times(-3)-2$ . »
2) « Si $ac\equiv bc\pmod n$ alors $a\equiv b\pmod n$ , comme dans les entiers. »
3) « Tout élément non nul possède un inverse modulo $n$ . »
4) « Pour calculer $3^{100}$ modulo 7, on réduit l'exposant modulo 7. »
5) « L'algorithme d'Euclide devient lent quand les nombres sont grands, il faut donc éviter de l'utiliser en cryptographie. »

Tape tes réponses, la page te dit juste ou faux 0/11

1)

-17 \bmod 5

La raison est que

2)

On ne peut simplifier par

c

que si

Le contre-exemple est

3)

Éléments inversibles modulo 6

L'affirmation n'est vraie que si

4)

100 \bmod 6

Le résultat juste

Le résultat faux obtenu en réduisant modulo 7

5)

Divisions au plus, pour deux nombres de 600 chiffres

L'algorithme d'Euclide étendu est

Voir la correction

Réponses

1) FAUX : $-2$ n'est pas un reste valide. $-17 = 5(-4)+3$ , donc le reste vaut 3
2) FAUX : on ne simplifie que par un $c$ inversible. $2\times3 \equiv 4\times3 \pmod 6$ et pourtant $2 \not\equiv 4$
3) FAUX : seuls 1 et 5 sont inversibles modulo 6. Il faut $\mathrm{pgcd}(a,n)=1$
4) FAUX : l'exposant se réduit modulo $p-1=6$ , non modulo 7. On trouve 4, et non 2
5) FAUX : moins de 3000 divisions pour deux nombres de 600 chiffres. Euclide étendu est un pilier de RSA

1)

FAUX. L'égalité écrite est correcte, mais $-2$ n'est PAS un reste valide : la division euclidienne impose $0\leq r<n$ , donc ici $0\leq r<5$ . Il faut choisir $q=-4$ : $-17=5\times(-4)+3$ , donc $-17\bmod 5=3$ . C'est aussi ce que renvoie Python. La confusion vient des langages comme C ou Java, dont l'opérateur suit une autre convention et renvoie effectivement $-2$ : le langage n'a pas tort, il ne calcule simplement pas le reste euclidien.

2)

FAUX. On ne peut simplifier par $c$ que si $c$ est INVERSIBLE modulo $n$ , c'est-à-dire premier avec $n$ . Contre-exemple : $2\times 3\equiv 4\times 3\pmod 6$ , car $6\equiv 12\equiv 0$ , et pourtant $2\not\equiv 4\pmod 6$ . La règle correcte est que $ac\equiv bc\pmod n$ entraîne $a\equiv b\pmod{\frac{n}{\mathrm{pgcd}(c,n)}}$ , ce qui ne redonne le module de départ que si le PGCD vaut 1.

3)

FAUX. L'inverse de $a$ modulo $n$ existe si et seulement si $\mathrm{pgcd}(a,n)=1$ . Modulo 6, les éléments 2, 3 et 4 n'ont pas d'inverse, puisqu'ils partagent un facteur avec 6 ; seuls 1 et 5 en ont. L'affirmation n'est vraie que lorsque $n$ est PREMIER, cas où tous les éléments non nuls sont premiers avec $n$ par définition.

4)

FAUX, et l'erreur est d'un seul cran mais elle change tout. Le petit théorème de Fermat donne $3^{6}\equiv 1\pmod 7$ , donc c'est modulo $p-1=6$ que l'on réduit l'exposant, et non modulo 7. On a $100\equiv 4\pmod 6$ , donc $3^{100}\equiv 3^{4}=81\equiv 4$ . Réduire modulo 7 donnerait $100\equiv 2$ , donc $3^{2}=9\equiv 2$ , résultat faux. Règle : la base se réduit modulo $n$ , l'exposant modulo $p-1$ .

5)

FAUX, c'est exactement le contraire. Le théorème de Lamé garantit que le nombre de divisions est au plus environ 5 fois le nombre de CHIFFRES du plus petit nombre : pour deux nombres de 600 chiffres, cela fait moins de 3000 divisions, soit une fraction de milliseconde. C'est cette efficacité qui permet de calculer l'exposant de déchiffrement d'une clé RSA, et l'algorithme d'Euclide étendu est donc au contraire un pilier de la cryptographie moderne.

Exercice 9 : Problème : les clés de contrôle, de l'ISBN au numéro de carte

Chaque code que vous tapez, numéro de livre, de carte bancaire ou de sécurité sociale, porte un chiffre supplémentaire dont le seul rôle est de détecter vos fautes de frappe. Ce chiffre est un reste.

a) Un code ISBN à treize chiffres vérifie que la somme pondérée par $1,3,1,3,\dots$ des treize chiffres est un multiple de 10. La figure donne les douze premiers chiffres et une somme pondérée de 97. Calculez la clé.
b) Vérifiez que le code complet satisfait bien la condition.
c) Un utilisateur se trompe d'un chiffre en tapant le code. Démontrez que l'erreur est toujours détectée.
d) Il intervertit deux chiffres voisins. Montrez que l'erreur est détectée SAUF dans un cas précis, et donnez un exemple.
e) Le code ISBN à dix chiffres utilisait les poids $10,9,\dots,1$ et le module 11, avec un $X$ pour la valeur 10. Pourquoi 11 détecte-t-il mieux que 10 ?

Tape tes réponses, la page te dit juste ou faux 0/11

a)

Somme pondérée des douze premiers chiffres

Clé

b)

Somme totale

Son reste modulo 10

c)

L'erreur passerait inaperçue si

Cela tient à ce que

d)

La variation de la somme vaut

Écart

\lvert a-b \rvert

qui rend l'erreur invisible

Somme pondérée du code fautif

e)

11 détecte mieux parce qu'il est

Le prix à payer est

Voir la correction

Réponses

a) La clé vaut 3, puisque $97+3 = 100$
b) $100 \equiv 0 \pmod{10}$ : le code est valide
c) La somme varie de $w(d'-d)$ , qui ne peut être multiple de 10 : 3 est premier avec 10
d) La somme varie de $2(a-b)$ : l'erreur échappe quand $\lvert a-b \rvert = 5$
e) 11 est PREMIER : aucun diviseur de zéro, donc toutes les interversions sont détectées, au prix du caractère X

a)

Dans la convention ISBN-13, la clé est le treizième chiffre et elle porte le poids 1, puisque les poids alternent en commençant par 1. Il faut donc que $97+c$ soit un multiple de 10, avec $0\leq c\leq 9$ . Le multiple de 10 immédiatement supérieur à 97 est 100, donc $c=3$ . Formule générale : $c=\left(10-\left(S\bmod 10\right)\right)\bmod 10$ , et le dernier modulo sert au seul cas où $S$ est déjà multiple de 10, où la clé vaut 0 et non 10.

b)

Somme totale : $97+3=100$ , qui est bien un multiple de 10 puisque $100\equiv 0\pmod{10}$ ✓. Le code complet est donc valide, et c'est cette vérification, et non le calcul de la clé, que la caisse d'une librairie effectue à chaque scan.

c)

Supposons qu'un chiffre de poids $w$ passe de $d$ à $d'$ . La somme change de $w\left(d'-d\right)$ , avec $w$ valant 1 ou 3 et $d'-d$ compris entre $-9$ et 9, non nul. Pour que l'erreur passe inaperçue, il faudrait que $w\left(d'-d\right)\equiv 0\pmod{10}$ . Avec $w=1$ : il faudrait $10$ divise $d'-d$ , impossible pour un écart non nul de moins de 10. Avec $w=3$ : comme $\mathrm{pgcd}(3,10)=1$ , on peut simplifier par 3 et l'on retombe sur la même impossibilité. Toute erreur d'UN chiffre est donc détectée, et c'est précisément parce que 3 est premier avec 10.

d)

En intervertissant deux chiffres voisins $a$ et $b$ portant les poids 1 et 3, la somme passe de $a+3b$ à $b+3a$ , soit une variation de $2\left(a-b\right)$ . L'erreur échappe au contrôle si $2\left(a-b\right)\equiv 0\pmod{10}$ , c'est-à-dire si $a-b\equiv 0\pmod 5$ , donc si $\left|a-b\right|=5$ . EXEMPLE : le code $9782723456807$ est valide, de somme 103 plus une clé 7, soit 110. En intervertissant le 2 et le 7 des positions 4 et 5, on obtient $9782\!\to\!9787\dots$ , dont la somme pondérée devient 113 plus 7, soit 120, encore multiple de 10 : la faute de frappe n'est PAS détectée. C'est la faiblesse connue de l'ISBN-13, et c'est un défaut sérieux puisque l'interversion de deux chiffres voisins est l'erreur de saisie la plus courante.

e)

Parce que 11 est PREMIER alors que 10 ne l'est pas. Modulo un nombre premier, tout coefficient non nul est inversible et il n'existe aucun diviseur de zéro : intervertir deux chiffres $a$ et $b$ de poids $w_{i}$ et $w_{j}$ fait varier la somme de $(w_{i}-w_{j})(a-b)$ ; comme $w_{i}-w_{j}$ est non nul et compris entre $-9$ et 9, 11 ne le divise pas, et cette variation ne peut s'annuler modulo 11 que si 11 divise $a-b$ , c'est-à-dire si $a=b$ : il n'y a pas eu d'erreur. L'ISBN-10 détectait donc TOUTES les interversions de deux chiffres, y compris non voisins. Le prix à payer est qu'une clé peut valoir 10, d'où le caractère $X$ , ce qui a été jugé gênant pour les codes-barres et explique l'abandon du système au profit du moins bon mais plus commode ISBN-13.

Exercice 10 : Problème : le chiffrement RSA en petits nombres

Tout ce qui précède se rassemble ici. Le chiffrement RSA repose sur l'inverse modulaire, le petit théorème de Fermat et l'exponentiation rapide, et il tient sur une page tant qu'on prend des nombres premiers minuscules.

a) On choisit $p=11$ et $q=13$ . Calculez le module $n=pq$ et l'indicatrice $\varphi(n)=(p-1)(q-1)$ .
b) On choisit l'exposant public $e=7$ . Vérifiez qu'il convient, puis calculez l'exposant privé $d$ , inverse de $e$ modulo $\varphi(n)$ .
c) Chiffrez le message $M=9$ par $C=M^{e}\bmod n$ .
d) Déchiffrez $C$ par $M=C^{d}\bmod n$ et vérifiez que l'on retrouve 9.
e) Pourquoi un attaquant qui connaît $n$ et $e$ ne peut-il pas retrouver $d$ en pratique, alors que la méthode est évidente en principe ?

Tape tes réponses, la page te dit juste ou faux 0/13

a)

n

\varphi(n)

b)

pgcd(7, 120)

d

Vérification

7d \bmod 120

c)

9^{4} \bmod 143

126 \times 81 \bmod 143

C

d)

M

retrouvé

Le théorème qui garantit ce retour est

e)

En principe, il suffirait de

En pratique, c'est impossible parce que

Cette difficulté est

Voir la correction

Réponses

a) $n = 143$ et $\varphi(n) = 120$
b) $\mathrm{pgcd}(7,120)=1$ et $d = 103$ , puisque $7 \times 103 = 721 = 6(120)+1$
c) $C = 48$
d) $M = 48^{103} \bmod 143 = 9$ , par le théorème d'Euler
e) Il faudrait factoriser $n$ ; sur 600 chiffres, aucun algorithme connu n'y parvient, et cette difficulté est constatée, non démontrée

a)

$n=11\times 13=143$ . $\varphi(n)=(11-1)(13-1)=10\times 12=120$ . Le module $n$ est PUBLIC, il fait partie de la clé publique ; $\varphi(n)$ est SECRET, car le connaître revient à connaître la clé privée, comme la question e le montrera.

b)

Il faut $\mathrm{pgcd}(e,\varphi(n))=1$ : ici $\mathrm{pgcd}(7,120)=1$ , car 7 est premier et ne divise pas 120. L'exposant convient. On cherche $d$ tel que $7d\equiv 1\pmod{120}$ . Par Euclide étendu ou par essai guidé : $7\times 103=721=720+1=6\times 120+1$ , donc $d=103$ . Vérification : $721\bmod 120=1$ ✓.

c)

$C=9^{7}\bmod 143$ . On procède par exponentiation rapide en réduisant à chaque étape : $9^{2}=81$ ; $9^{4}=81^{2}=6561$ , et $6561=143\times 45+126$ donc $9^{4}\equiv 126$ ; enfin $9^{7}=9^{4}\times 9^{2}\times 9\equiv 126\times 81\times 9$ . On calcule $126\times 81=10\,206\equiv 53$ car $10\,206=143\times 71+53$ , puis $53\times 9=477\equiv 48$ car $477=143\times 3+48$ . Donc $C=48$ . Le message chiffré est 48.

d)

$M=48^{103}\bmod 143$ . Le nombre $48^{103}$ compte 174 chiffres et l'on ne l'écrit évidemment jamais : l'exponentiation rapide réduit modulo 143 après chaque carré, et l'on obtient $M=9$ ✓, le message d'origine. Le théorème qui garantit ce retour est celui d'Euler, généralisation du petit théorème de Fermat : comme $ed\equiv 1\pmod{\varphi(n)}$ , on a $M^{ed}\equiv M\pmod n$ .

e)

En principe la méthode est immédiate : il suffit de factoriser $n$ pour retrouver $p$ et $q$ , d'en déduire $\varphi(n)$ , puis $d$ par Euclide étendu. Ici, avec $n=143$ , un élève trouve $11\times 13$ en quelques secondes. Mais dans un usage réel $n$ compte environ 600 chiffres, et aucun algorithme connu ne sait factoriser un tel nombre en un temps raisonnable : les meilleurs demanderaient des milliards d'années. Toute la sécurité repose donc sur une ASYMÉTRIE de coût, multiplier deux grands nombres premiers est instantané, retrouver les facteurs ne l'est pas. Remarquez que rien de tout cela n'est démontré : on ne sait pas prouver que la factorisation est difficile, on constate seulement que personne n'a trouvé comment la rendre facile.

Exercices corrigés : l'arithmétique modulaire (201-N11)

Rappel de cours

Calculs : les restes à calculer

Exercice 0.1 : Réduire modulo n : dix calculs directs

Calculs : les inverses et les congruences à résoudre

Exercice 0.2 : Inverser et résoudre modulo n : huit calculs directs

Partie A : les bases (/50)

Exercice 1 : La division euclidienne et le reste

Exercice 2 : Les congruences et leurs règles de calcul

Exercice 3 : Calculer dans les entiers modulo n

Exercice 4 : Le PGCD et l'algorithme d'Euclide

Exercice 5 : L'inverse modulaire et les équations de congruence

Partie B : problèmes et raisonnement (/50)

Exercice 6 : Bézout et l'algorithme d'Euclide étendu

Exercice 7 : Le petit théorème de Fermat et l'exponentiation rapide

Exercice 8 : Cinq affirmations à corriger

Exercice 9 : Problème : les clés de contrôle, de l'ISBN au numéro de carte

Exercice 10 : Problème : le chiffrement RSA en petits nombres

Voir aussi

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