Quel jour sera-t-on dans cent jours ?
L’arithmétique modulaire calcule avec les restes d’une division : l’heure sur une horloge, le jour de la semaine, la clé d’un numéro. Avec le PGCD et les nombres premiers, elle sert à vérifier des numéros et, plus tard, à chiffrer des messages.
Il est 15 h et un cours dure 10 h : il finit à 1 h du matin, pas à 25 h. On ne garde que le reste dans la division par 24.
À la fin de cette leçon
Remarque
Je peux calculer avec des restes, un PGCD et des nombres premiers.
Mots-clés
| Mot | Ce que ça veut dire | Exemple |
|---|---|---|
| Modulo | le reste d’une division entière | 25 modulo 24 = 1 |
| Congruent | qui a le même reste dans la division par le même nombre | |
| PGCD | le plus grand nombre qui divise deux entiers | |
| Nombre premier | un entier supérieur à 1 divisible seulement par 1 et par lui-même | 13 |
| Inverse modulaire | un nombre qui, multiplié par a, donne le reste 1 | |
| Clé de contrôle | un chiffre calculé qui sert à détecter une erreur de frappe |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Modulo garde seulement le reste
Diviser 17 par 5 donne 3 et il reste 2. On dit que 17 modulo 5 vaut 2.
Deux nombres sont congruents modulo 5 s’ils ont le même reste. 17 et 22 le sont : tous deux laissent 2. L’horloge compte modulo 24, la semaine modulo 7.
Exemple travaillé : la semaine tourne modulo 7
| Dans combien de jours | Division par 7 | Reste | Jour si on part un lundi |
|---|---|---|---|
| 3 | 3 = 0 × 7 + 3 | 3 | Jeudi |
| 7 | 7 = 1 × 7 + 0 | 0 | Lundi |
| 10 | 10 = 1 × 7 + 3 | 3 | Jeudi |
| 100 | 100 = 14 × 7 + 2 | 2 | Mercredi |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Le reste de 17 par 5
echo $((17 % 5))Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Le reste de 100 par 7
python3 -c "print(100 % 7)"Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Erreur fréquente
Attention
Beaucoup pensent que le reste de -7 par 3 est le même partout. Ce n’est pas le cas. Python rend toujours un reste positif ou nul, ici 2. Le shell et le langage C gardent le signe et rendent -1. Testez avant de vous fier à un langage.
Un reste négatif en Python
python3 -c "print(-7 % 3)"Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Le même calcul dans le shell
echo $((-7 % 3))Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Le PGCD se trouve par divisions successives
Le PGCD de 84 et 36 est le plus grand nombre qui divise les deux : 12. Euclide l’a trouvé sans lister les diviseurs.
On divise 84 par 36 : il reste 12. Puis 36 par 12 : il reste 0. Le dernier reste non nul, 12, est le PGCD.
Exemple travaillé : le PGCD de 84 et 36
| Étape | Division | Reste |
|---|---|---|
| 1 | 84 = 36 × 2 + 12 | 12 |
| 2 | 36 = 12 × 3 + 0 | 0 |
| Réponse | Le dernier reste non nul | 12 |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
L’algorithme d’Euclide en Python
# L’algorithme d’Euclide : on remplace (a, b) par (b, reste de a par b).
a = 84
b = 36
while b != 0:
reste = a % b
print(a, "=", b, "x", a // b, "+", reste)
a = b
b = reste
print("PGCD :", a)
# Changez a en 252 et b en 105 puis relancez : prévoyez le PGCD.
Vérifier avec la bibliothèque
python3 -c "import math; print(math.gcd(84, 36))"Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Un nombre premier n’a que deux diviseurs
Un nombre premier a exactement deux diviseurs : 1 et lui-même. 13 est premier. 15 ne l’est pas, car 3 le divise.
Pour tester n, on cherche un diviseur parmi 2, 3, 4 et ainsi de suite. Si aucun ne convient, n est premier. 1 n’est pas premier.
Les nombres premiers avant 30
python3 -c "print([n for n in range(2, 30) if all(n % d for d in range(2, n))])"Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Inverse modulaire : le PGCD doit valoir 1
Modulo 7, quel nombre x vérifie 3 fois x = 1 ? On essaie : 3, 6, 2, 5, 1. Le cinquième rang donne 1, donc x = 5 est l’inverse modulaire de 3.
Il existe seulement si le PGCD de 3 et 7 vaut 1. Modulo 8, le nombre 4 n’a pas d’inverse : 4 et 8 ont pour PGCD 4.
Exemple travaillé : 3 fois x modulo 7
| x | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 3 × x | 3 | 6 | 9 | 12 | 15 | 18 |
| Reste par 7 | 3 | 6 | 2 | 5 | 1 | 4 |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
L’inverse de 3 modulo 7
python3 -c "print(pow(3, -1, 7), pow(2, 10, 1000))"Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Une clé de contrôle détecte une erreur
Les numéros de sécurité sociale français se terminent par une clé. On prend les treize premiers chiffres comme un grand nombre n. La clé vaut 97 moins le reste de n par 97.
Pour l’exemple 1850575123456, le reste est 24, donc la clé est 73. Une erreur de frappe change presque toujours le reste, et la clé ne colle plus.
Calculer la clé de l’exemple
python3 -c "print(1850575123456 % 97, 97 - 1850575123456 % 97)"Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Pour aller plus loin
Changez un chiffre du numéro d’exemple dans la dernière commande et relancez-la. Notez la nouvelle clé : elle n’est plus 73.
Puis cherchez deux entiers inférieurs à 20 dont le PGCD vaut 1 sans qu’aucun des deux soit premier. Par exemple 8 et 9 : écrivez pourquoi.