La congruence (le modulo)

D’où ça vient ?

La congruence a été, pour la première fois, formellement étudiée à la fin du 18ème siècle et au tout début du 19ème siècle par Carl Friedrich Gauss, le « master » des mathématiciens.

Il a laissé son nom à la courbe en cloche dite « courbe de Gauss ».

Auparavant, on utilisait la congruence sans avoir conscience de ses propriétés, tout comme on sait additionner 2 carottes et 3 carottes sans avoir conscience que c’est un calcul de somme en arithmétique.

C’est bien mignon tout ça, mais sinon, qu’est-ce que c’est ?

Le principe

La congruence est une structure mathématique, c’est à dire un ensemble de règles, qui permet de relier des nombres entiers entre eux dans un ensemble fini.

C’est à dire que si on considère une congruence de module (ou modulo) n (on verra plus loin ce qu’est un module), on a les propriétés suivantes :

$$ a \equiv a \pmod{n} $$ $$ \text{si } a \equiv b \pmod{n} \quad \text{alors } b \equiv a \pmod{n} $$ $$ \text{si } a \equiv b \pmod{n} \quad \text{et } b \equiv c \pmod{n} \quad \text{alors } a \equiv c \pmod{n} $$ $$ \text{si } a \equiv b \pmod{n} \quad \text{et } c \equiv d \pmod{n} \quad \text{alors } a+c \equiv b+d \pmod{n} \quad \text{et } a \times c \equiv b \times c \pmod{n} $$

Et la vous vous dites « J’ai rien compris. Pourquoi il y a trois barres dans son égal ? Ça veut dire quoi ce mod ? Tant de questions ? »

Ne vous inquiétez pas. On va faire des exemples et des représentations plus claires.

On boucle, on boucle

Une autre façon de se représenter la congruence et le modulo, c’est sous la forme d’une boucle ou d’un cycle.

Un petit exemple, les minutes

Imaginez que vous regardez une horloge et vous ne vous occupez que de l’aiguille des minutes.

Vous voulez additionner 45 minutes et 30 minutes mais vous ne vous préoccupez pas de l’heure (juste l’aiguille des minutes). Vous trouvez quoi ?

15 minutes, non ?

Félicitations, vous avez fait un calcul de congruence de module 60 (ou modulo 60).

Et vous pouvez ajouter des nombres bien plus grands que 60 (ou n’importe quel autre module). Il faut soustraire 60 du résultat autant qu’on peut. Le résultat doit être compris dans l’ensemble (donc ici entre 0 et 59).

Combien font 59 + 258 minutes modulo 60 ?

Réponse à la fin de ce billet de blog.

Un deuxième petit exemple, les heures

Maintenant, avec les heures. Vous ne regardez que l’aiguille des heures (vous oubliez les minutes). Vous ajoutez 5 heures à 8 heures. Vous trouvez quoi ? Attention, c’est une horloge.

1 heure, non ? (vu qu’une horloge n’affiche que 12 heures)

Vous avez fait un calcul de congruence de module 12.

Et du coup, pourquoi un signe égal avec trois traits ? Et bien, parce que ce résultat dans le deuxième exemple n’est pas égal à 1, vu qu’on a enlevé des heures en trop. Donc on le note avec ce signe qu’on appelle « congru ».

Vous voyez qu’on peut faire des additions avec des nombres immenses tout en gardant un résultat dans des nombres limités (un ensemble fini). La taille de la congruence limite la possibilité des résultats. Ici, par exemple, l’ensemble contient 12 nombres, les 12 heures d’une horloge.

Bien sûr, comme c’est un cycle, ça marche aussi en soustrayant des heures et avec des nombres entiers négatifs. Il faut bien sûr, additionner ensuite le module pour revenir dans l’ensemble de nombres (donc ici entre 0 et 11).

Combien font donc : 2-18 heures modulo 12 ?

Réponse à la fin de ce billet de blog.

Encore un exemple, les doigts

Si vous considérez les doigts d’une main, vous avez une congruence de 5 (généralement) et les doigts de 2 mains, vous avez une congruence de 10.

Pas convaincus ?

Prenez juste une main et comptez avec vos doigts 3+4, combien avez-vous de doigts qui restent ?

2, je pense.

Maintenant, prenez 2 mains et comptez 8+9, combien avez-vous de doigts qui restent ?

7, non ?

J’utilise le terme « reste » exprès. Vous allez voir.

Et le reste ?

On peut voir aussi la congruence comme le reste d’une division (euclidienne, pour les connaisseurs).

Le dénominateur d’une division (le nombre en dessous) est le module et quand vous avez fini votre division, ce qui reste est le « reste », justement.

Attention, il est important de se rappeler que cela fonctionne avec des entiers donc pas de virgule, vous arrêtez votre division avant que le reste n’ait une virgule.

Donc, si on divise 3 par 2, on a quel reste ?

1 bien sûr.

Et si on divise 5 par 2, quel reste ?

1 aussi, pas mal.

Du coup, ça veut dire que 1 ≡ 3 mod(2) et 1 ≡ 5 mod(2), on est d’accord ?

Et donc :

$$ 1 \equiv 3 \pmod{2} \equiv 5 \pmod{2} $$

Maintenant, est-ce que le reste de 33/26 et le reste de 85/26 sont congrus ?

Réponses

Combien font 59 + 258 minutes modulo 60 ?

$$ 59+258 = 317 \equiv 317-60 \times 5 \pmod{60} $$

(on a 5 fois 60 qui est plus petit que 317)

$$ \equiv 317-300 \pmod{60} \equiv 17 \pmod{60} $$

Donc :

$$ 59+258 \equiv 17 \pmod{60} $$

Combien font : 2-18 heures modulo 12 ?

$$ 2-18 = -16 \equiv -16+12 \pmod{12} \equiv -4 \pmod{12} $$

(c’est encore négatif, donc pas entre 0 et 11)

$$ \equiv -4+12 \pmod{12} \equiv 8 \pmod{12} $$

Donc : $$ 2-18 \equiv 8 \pmod{12} $$

Est-ce que le reste de 33/26 et le reste de 85/26 sont congrus ?

$$ 33/26 = (26+7)/26 $$

donc le reste est 7.

$$ 85/26 = (26+59)/26 $$

59 est plus grand que 26, on continue

$$ = (26+26+33)/26 $$

tiens donc 33, comme pour la première division, on continue

$$ = (26+26+26+7)/26 $$

donc le reste est 7.

Donc, oui, le reste de 33/26 et le reste de 85/26 sont congrus.