Arithmétique modulaire — calcul d’horloge, mod et congruence

L’arithmétique modulaire consiste à travailler avec les restes après division par un entier positif fixé appelé le module. Si deux nombres laissent le même reste, ils se comportent de la même façon dans ce système modulaire, d’où l’expression calcul d’horloge.

Sur une horloge de $12$ heures, $13$ heures tombe sur $1$ heure, et $29$ heures tombe au même endroit que $5$ heures. Ce cycle qui se répète donne l’intuition de base de l’arithmétique modulaire.

Ce que signifie mod en arithmétique modulaire

Pour un entier $a$ et un entier positif $n$, l’expression $a \bmod n$ désigne le reste lorsque $a$ est divisé par $n$.

Exemple :

$$29 \bmod 12 = 5$$

car

$$29 = 12 \cdot 2 + 5$$

Le module est $12$, donc ajouter ou soustraire $12$ ne change pas la position d’arrivée dans le cycle.

Ce que signifie la congruence modulo $n$

La congruence est la façon formelle de dire que deux entiers se comportent de la même manière modulo $n$.

$$a \equiv b \pmod n$$

signifie que $a$ et $b$ laissent le même reste lorsqu’on les divise par $n$. Un critère équivalent est

$$n \mid (a-b)$$

ce qui signifie « $n$ divise $a-b$ ».

Donc

$$29 \equiv 5 \pmod{12}$$

car $29 - 5 = 24$, et $12$ divise $24$.

Cette distinction est importante :

• $29 \bmod 12 = 5$ est une affirmation sur un reste.
• $29 \equiv 5 \pmod{12}$ est une affirmation de congruence.

Ces deux idées sont liées, mais elles ne sont pas interchangeables.

Exemple résolu : $29$ heures après $8$ heures

Supposons qu’il soit $8$ heures maintenant et que vous vouliez connaître l’heure $29$ heures plus tard sur une horloge de $12$ heures.

Commencez par réduire $29$ modulo $12$ :

$$29 \bmod 12 = 5$$

Donc ajouter $29$ heures a le même effet qu’ajouter $5$ heures :

$$8 + 29 \equiv 8 + 5 \pmod{12}$$

Puis

$$8 + 29 \equiv 13 \equiv 1 \pmod{12}$$

L’horloge indique donc $1$ heure.

L’étape clé est la réduction. En modulo $12$, remplacer $29$ par $5$ conserve la même réponse et rend le calcul plus simple.

Pourquoi réduire d’abord simplifie les problèmes

Les grands nombres sont souvent plus faciles à manipuler après les avoir remplacés par un plus petit nombre congru.

Par exemple, modulo $7$,

$$100 \equiv 2 \pmod 7$$

car $100 - 2 = 98$ est divisible par $7$. Si le problème ne s’intéresse qu’aux valeurs modulo $7$, vous pouvez travailler avec $2$ au lieu de $100$.

Erreurs fréquentes

Confondre égalité et congruence

$29 \equiv 5 \pmod{12}$ ne signifie pas que $29 = 5$. Cela signifie qu’ils appartiennent à la même classe de restes modulo $12$.

Oublier que le module compte

$17 \equiv 5 \pmod{12}$ est vrai, mais $17 \equiv 5 \pmod{10}$ est faux. Une congruence est toujours liée à un module précis.

Traiter mod comme une division ordinaire

$29 \bmod 12$ est le reste $5$, pas le quotient $2$ et pas la fraction $29/12$.

Supposer que l’opérateur logiciel % suit toujours la même convention mathématique

Pour les nombres positifs, l’opérateur % des langages de programmation correspond souvent à l’idée de reste que les élèves apprennent d’abord. Avec les nombres négatifs, les conventions peuvent varier, donc le résultat peut ne pas correspondre au plus petit reste non négatif utilisé dans beaucoup de cours de mathématiques.

Où l’arithmétique modulaire est utilisée

On rencontre l’arithmétique modulaire chaque fois que des valeurs se répètent en cycles : horloges, jours de la semaine, systèmes de chiffres de contrôle, hachage et de nombreuses parties de la théorie des nombres.

Elle apparaît aussi en cryptographie, mais l’idée de base reste la même : les nombres sont regroupés selon leurs restes, et les nombres congrus peuvent être traités comme équivalents à l’intérieur de ce système.

Essayez un problème similaire

Quel jour de la semaine sera-t-on $100$ jours après un lundi ? Comme les jours se répètent modulo $7$, commencez par réduire $100$ modulo $7$ avant de répondre.

Si vous voulez un autre cas à comparer, essayez votre propre version dans GPAI Solver et voyez si réduire d’abord rend le travail plus court.