Que signifie le symbole $\equiv$ ?

On le lit « est congru à ». $17 \equiv 5 \pmod{12}$ dit que 17 et 5 ont le même reste dans la division par 12 (tous deux ont le reste 5). C'est plus faible que $=$ : des nombres congrus peuvent être différents tout en tombant au même endroit du cadran.

Pourquoi ai-je le droit de réduire les nombres d'abord ?

Écris $a = pn + r$ et $b = qn + s$. Alors $a + b = (p + q)n + (r + s)$ et $a \times b = (pqn + ps + qr)n + rs$. Les parties avec $n$ sont des multiples de $n$ et ne laissent aucun reste, donc seuls $r + s$ et $r \times s$ décident du résultat.

Où utilise-t-on l'arithmétique modulaire en dehors de l'école ?

Dans les clés de contrôle (codes-barres, ISBN, l'IBAN d'un compte bancaire, vérifié modulo 97), en informatique (tables de hachage, générateurs de nombres aléatoires) et en cryptographie : la méthode RSA qui protège la banque en ligne calcule avec des nombres géants modulo un produit de deux nombres premiers.

Ressources enseignants

Arithmétique modulaire

Apprends l'arithmétique de l'horloge : restes, a mod n, congruence modulo n, et comment s'en servir pour les jours de la semaine, les clés de contrôle et le dernier chiffre de puissances géantes.

Avancé25 minLeçon

Partager dans Classroom

Fiche d'exercices à imprimer

Définition

L'arithmétique modulaire est le calcul avec des restes. Tu fixes un nombre entier

n \geq 2

, le module, et d'un nombre tu ne gardes que son reste dans la division par

n

a = q \times n + r, \qquad a \bmod n = r, \qquad 0 \leq r \leq n - 1

Par exemple,

17 \bmod 5 = 2

car

17 = 3 \times 5 + 2

Deux nombres sont congrus modulo n quand ils ont le même reste. Cela revient à dire que

n

divise leur différence :

a \equiv b \pmod{n} \iff n \text{ divise } a - b

Ainsi

38 \equiv 14 \pmod{12}

, car

38 - 14 = 24 = 2 \times 12

(les deux ont le reste

2

Une horloge fonctionne exactement ainsi : après 12 heures l'aiguille revient à son point de départ, donc 15 heures et 3 heures sont la même position,

15 \equiv 3 \pmod{12}

. Dans les sommes, les différences et les produits, tu peux remplacer chaque nombre par son reste d'abord, puis réduire encore une fois le résultat à la fin.

Essaie tout de suite

Combien vaut

23 \bmod 5

Exemples résolus

Calcule

47 \bmod 6

Trouve le plus grand multiple de 6 qui ne dépasse pas 47

6 \times 7 = 42

, alors que

6 \times 8 = 48

est déjà trop grand →

42

Écris 47 sous la forme quotient fois 6 plus reste

47 = 7 \times 6 + 5

→ reste

5

Vérifie que le reste est compris entre 0 et 5

0 \leq 5 \leq 5

, c'est donc un reste valable →

47 \bmod 6 = 5

Réponse: $47 \bmod 6 = 5$ , donc $47 \equiv 5 \pmod{6}$ . Le quotient $7$ ne fait pas partie de la réponse.

Erreurs courantes

Écrire $-3 \bmod 12 = -3$ (ou $3$ )

Pourquoi c'est faux: Un reste doit être l'un des nombres $0, 1, \ldots, n - 1$ . En reculant de 3 heures à partir de midi, on ne tombe ni sur un nombre négatif ni sur 3.

Correct: Ajoute le module jusqu'à ce que le nombre soit dans l'intervalle : $-3 + 12 = 9$ , donc $-3 \bmod 12 = 9$ .

Dire que 9 heures plus 4 heures donne 13 heures sur une horloge de 12 heures

Pourquoi c'est faux: La somme $9 + 4 = 13$ est juste, mais la dernière réduction manque. Chaque résultat doit être réduit encore une fois.

Correct: $13 \bmod 12 = 1$ : l'horloge indique 1.

Donner le quotient au lieu du reste : $47 \bmod 6 = 7$

Pourquoi c'est faux: $47 \div 6 = 7$ reste $5$ . L'opération mod ne garde que ce qui reste, pas le nombre de fois que 6 entre dans 47.

Correct: $47 \bmod 6 = 5$ , car $47 = 7 \times 6 + 5$ .

Réduire l'exposant par le module : $2^9 \bmod 7$ devient $2^2 = 4$ parce que $9 \bmod 7 = 2$

Pourquoi c'est faux: Tu peux réduire la base modulo $n$ , mais pas l'exposant. L'exposant suit la longueur du cycle des puissances, qui vaut ici 3 et non 7.

Correct: Les puissances de 2 modulo 7 sont $2, 4, 1, 2, 4, 1, \ldots$ (cycle de longueur 3). $9 \bmod 3 = 0$ , donc $2^9 \equiv 1 \pmod{7}$ . Vérification : $512 = 73 \times 7 + 1$ .

Visuel interactif

9 heures plus 100 heures : compte les tours

12 positions sur le cadran : modulo 12

Départ

Ajouter

Pars de 9 et avance de 100 heures.

Les jours de la semaine modulo 7 : devine d'abord, puis regarde

7 positions sur le cadran : modulo 7

Où l'aiguille va-t-elle s'arrêter ? Touche la position sur le cadran.

2 + 100 ≡ ? (mod 7)

Pars de mer et avance de 100 jours.

Congrus modulo 12 : même position sur le cadran

12 positions sur le cadran : modulo 12

Premier nombre

Deuxième nombre

38 = 3 × 12 + 2

14 = 1 × 12 + 2

38 − 14 = 24 = 2 × 12

38 ≡ 14 (mod 12)

38 et 14 tombent sur la même position car leur différence 24 est un multiple de 12.

Nombres sur la position 2 : … -10, 2, 14, 26, 38 …

Les derniers chiffres des puissances de 3 (modulo 10) se répètent

10 positions sur le cadran : modulo 10

Base

Exposant

Multiplie par 3 encore et encore, et ne garde que le reste à chaque fois.

Bac à sable interactif

Calculatrice d'expressions

Essaie ceux-ci :

Historique

Aucun calcul pour l'instant

Exercices pratiques

18 exercices

Problème 1 sur 18

Facile

Combien vaut

23 \bmod 5

Pourquoi c'est important

L'arithmétique modulaire, ce sont les mathématiques de tout ce qui tourne en rond :

Le temps : les horloges comptent modulo 12 ou 24, les jours de la semaine modulo 7. Quelle heure sera-t-il dans 100 heures ? Quel jour serons-nous dans 100 jours ?
Les clés de contrôle : le dernier chiffre d'un code-barres (EAN-13) est choisi modulo 10, celui d'un ISBN-10 modulo 11, et l'IBAN d'un compte bancaire est vérifié modulo 97. Un seul chiffre mal tapé, et le contrôle échoue.
Les nombres géants : tu peux trouver de tête le dernier chiffre de $3^{100}$ (un nombre de 48 chiffres), car les derniers chiffres sont des restes modulo 10 et ils se répètent en cycle.
L'informatique : les tables de hachage, les générateurs de nombres aléatoires et le chiffrement RSA derrière la banque en ligne calculent tous modulo $n$ .

Tu connais déjà un cas : pair et impair, c'est simplement le calcul modulo 2 (reste 0 ou 1).

Applications dans le monde réel

Calendriers : quel jour serons-nous ?

Une semaine compte 7 jours, donc les jours de la semaine se répètent modulo 7. Les applications d'agenda, les horaires et les énigmes d'anniversaire s'en servent tout le temps.

Exemple:

Une année normale compte $365$ jours et $365 = 52 \times 7 + 1$ . Un anniversaire qui tombe un lundi cette année tombera donc un mardi l'an prochain (sauf si un 29 février se trouve entre les deux).

1Essaie par toi-même

Aujourd'hui, c'est mercredi. Ton voyage d'échange commence dans exactement 100 jours. Numérote les jours lundi $= 0$ , mardi $= 1$ , et ainsi de suite jusqu'à dimanche $= 6$ .

Quel jour de la semaine le voyage commence-t-il ?

Étape 1 : Choisis la bonne réponse

Choisis le jour :

Codes-barres et clés de contrôle

Le dernier chiffre de chaque code-barres EAN-13 est une clé de contrôle, choisie par un calcul modulo 10. Le lecteur la recalcule et refuse un code dont un chiffre a été mal lu.

Exemple:

Pour le code de livre $978030640615$ , la somme pondérée (coefficients $1, 3, 1, 3, \ldots$ ) vaut $93$ , et $93 \bmod 10 = 3$ . La clé est $10 - 3 = 7$ , donc le code complet est $9780306406157$ .

2Essaie par toi-même

Un magasin crée un code produit avec les 12 chiffres $400123456789$ . Les chiffres aux positions 1, 3, 5, ... comptent une fois, ceux aux positions 2, 4, 6, ... comptent trois fois. La clé de contrôle rend le total multiple de 10.

Quelle est la clé de contrôle ?

Étape 1 : Écris l'expression mathématique

Clé de contrôle :

Travail posté et horloge de 24 heures

Les horaires de train, les gardes à l'hôpital et les plans de vol utilisent l'horloge de 24 heures, c'est-à-dire le calcul modulo 24.

Exemple:

Une garde de nuit commence à 22 h et dure 9 heures : $22 + 9 = 31$ et $31 \bmod 24 = 7$ , elle se termine donc à 7 h.

3Essaie par toi-même

Un test de machine dans une usine commence à 19 h et dure 75 heures sans interruption.

À quelle heure (de 0 à 23) le test se termine-t-il ?

Étape 1 : Écris l'expression mathématique

Heure de fin :

Points clés

1 $a \bmod n$ est le reste de la division de $a$ par $n$ et vaut toujours l'un des nombres $0, 1, \ldots, n - 1$
2 $a \equiv b \pmod{n}$ signifie que $a$ et $b$ ont le même reste, ce qui revient à dire que $n$ divise $a - b$
3Une horloge calcule modulo 12, l'horloge de 24 heures modulo 24, les jours de la semaine modulo 7 et pair/impair modulo 2
4Dans les sommes, les différences et les produits, tu peux réduire chaque nombre d'abord, puis réduire encore le résultat
5Pour un nombre négatif, ajoute $n$ jusqu'à tomber dans $0, \ldots, n - 1$ : $-3 \bmod 12 = 9$
6Les puissances se répètent en cycles modulo $n$ : trouve la longueur du cycle et réduis l'exposant modulo cette longueur, pas modulo $n$

Questions fréquentes

Pour les nombres positifs, oui. Pour les nombres négatifs, beaucoup de langages de programmation donnent un résultat négatif, par exemple

-3

pour

-3

divisé par

12

. En mathématiques, le reste est toujours compris entre

0

n - 1

, donc

-3 \bmod 12 = 9

. La calculatrice de cette page fonctionne ainsi : mod(-3, 12) donne 9.

Glossaire

Module: Le nombre fixe $n$ par lequel on divise ; les restes sont $0, 1, \ldots, n - 1$ (12 pour une horloge, 7 pour les jours de la semaine)
Reste: Ce qui reste après la division : dans $a = q \times n + r$ avec $0 \leq r \leq n - 1$ , c'est $r$
a mod n: Le reste de la division de $a$ par $n$ , par exemple $17 \bmod 5 = 2$ et $-3 \bmod 12 = 9$
Congru modulo n: Deux nombres qui ont le même reste modulo $n$ , noté $a \equiv b \pmod{n}$ ; de façon équivalente, $n$ divise $a - b$
Longueur du cycle: Le nombre d'étapes après lequel les restes des puissances se répètent, par exemple 4 pour les derniers chiffres des puissances de 3
Clé de contrôle: Un chiffre ajouté à la fin d'un code (code-barres, ISBN), choisi pour qu'une somme pondérée soit divisible par 10 ou par 11

Carte des formules

Division euclidienne

a = q \times n + r, \quad 0 \leq r \leq n - 1

$r$ est $a \bmod n$, $q$ est le quotient

Congruence

a \equiv b \pmod{n} \iff n \mid (a - b)

Même reste, ou : la différence est un multiple de $n$

Réduire d'abord

(a + b) \bmod n = \big((a \bmod n) + (b \bmod n)\big) \bmod n

Cela marche aussi pour la soustraction et la multiplication

Nombres négatifs

x \bmod n = (x + k \times n) \bmod n

Ajoute un multiple de $n$ jusqu'à ce que le nombre tombe dans $0, \ldots, n - 1$ : $-3 + 12 = 9$

Défi du jourUn problème, trois essais

Plus sur ce sujet

Nombres pairs et impairs

Élémentaire15 min

Carrés parfaits et nombres carrés

Intermédiaire25 min