Trouver un reste

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$

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

100 heures sur une horloge

Il est 9 heures. Où pointera l'aiguille des heures dans 100 heures ?

Enlève les tours complets : un tour d'horloge dure 12 heures: $100 = 8 \times 12 + 4$, et 8 tours complets ne changent rien = $100 \bmod 12 = 4$

Ajoute les heures restantes au départ: $9 + 4 = 13$ = $13$

Réduis encore, car le cadran n'a pas de 13: $13 = 1 \times 12 + 1$ = $13 \bmod 12 = 1$

Answer: L'aiguille pointe sur 1. En une ligne : $9 + 100 = 109 = 9 \times 12 + 1$, donc $109 \equiv 1 \pmod{12}$.

Réduire d'abord, multiplier ensuite

Calcule $(38 \times 27) \bmod 5$ sans multiplier les grands nombres.

Réduis chaque facteur modulo 5: $38 = 7 \times 5 + 3$ et $27 = 5 \times 5 + 2$ = $38 \equiv 3$ et $27 \equiv 2 \pmod{5}$

Multiplie les restes: $3 \times 2 = 6$ = $6$

Réduis le produit: $6 = 1 \times 5 + 1$ = $1$

Vérifie avec le produit complet: $38 \times 27 = 1026 = 205 \times 5 + 1$ = même reste $1$

Answer: $(38 \times 27) \bmod 5 = 1$. En réduisant d'abord, le calcul $3 \times 2$ a suffi.

Remonter dans le calendrier

Aujourd'hui, c'est mercredi. Quel jour de la semaine était-ce il y a 30 jours ? Numérote les jours lundi $= 0$, mardi $= 1$, et ainsi de suite jusqu'à dimanche $= 6$.

Donne son numéro au jour d'aujourd'hui: lundi $= 0$, mardi $= 1$, mercredi $= 2$ = $2$

Remonter dans le temps, c'est soustraire: $2 - 30 = -28$ = $-28$

Trouve le reste entre 0 et 6 du nombre négatif: $-28 = (-4) \times 7 + 0$ = $-28 \bmod 7 = 0$

Retransforme le numéro en jour: Le jour $0$ est le lundi = lundi

Answer: Il y a 30 jours, c'était un lundi. Vérification : il y a 28 jours, c'était un mercredi (exactement 4 semaines), et deux jours plus tôt, c'est lundi.

Le dernier chiffre d'une puissance géante

Quel est le dernier chiffre de $3^{100}$ ?

Le dernier chiffre est le reste modulo 10. Écris les premières puissances: $3^1 = 3$, $3^2 = 9$, $3^3 = 27$, $3^4 = 81$ = derniers chiffres $3, 9, 7, 1$

Repère le cycle: $3^5 = 243$ se termine de nouveau par 3, car le dernier chiffre suivant ne dépend que du précédent = longueur du cycle $4$

Cherche où tombe l'exposant 100 dans le cycle: $100 = 25 \times 4 + 0$ = $100 \bmod 4 = 0$

Un reste 0 correspond à la dernière place du cycle: $3^{100} = (3^4)^{25} \equiv 1^{25} = 1 \pmod{10}$ = dernier chiffre $1$

Answer: $3^{100}$ se termine par $1$, alors que ce nombre a 48 chiffres.

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

Why: 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$.

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

Why: 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.

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

Why: $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$.

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

Why: 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$.

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.

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).

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.

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$.

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.

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.

Q: Est-ce que $a \bmod n$ est le même reste que celui de ma calculatrice ou de mon ordinateur ?

A: 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$ et $n - 1$, donc $-3 \bmod 12 = 9$. La calculatrice de cette page fonctionne ainsi : mod(-3, 12) donne 9.

Q: Que signifie le symbole $\equiv$ ?

A: 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.

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

A: É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.

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

A: 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.