Travailler avec des congruences

Maths expertes

Les maths, c’est clair comme deux et deux font quatre. Vraiment ? Alors pourquoi a-t-on vu en cours aujourd’hui \(2+2\equiv1\) ? Et \(1+1\equiv0\) ? C’est à n’y plus rien comprendre !

À l’école tu as appris à compter sur tes doigts. Je suppose que tu en as dix. Comment faire alors quand il y a 13 bonbons à compter ? Et bien on utilise une congruence modulo 10 ! Et on recommence à compter sur sa main gauche : 11 sur le pouce — le doigt numéro 1 — 12 sur l’index — le doigt numéro 2 et 13 sur le majeur — le doigt numéro 3.

Bon, d’accord, en maternelle on ne t’a pas parlé de congruence. Mais oui, tu as été habitué à travaillé avec 😊. Congruence modulo 7 pour les jours de la semaine, modulo 12 pour les mois de l’année ou les heures de la pendule.

Faisons un rapide tour d’horizon avant d’apprendre à être à l’aise en maths expertes.

Le calendrier perpétuel

Aujourd’hui nous sommes mercredi, le 3e jour de la semaine. Quel jour serons-nous dans 5 jours ? Et bien 3+5=8 et donc, euh, et donc, et donc… je vais regarder dans mon agenda 🙁

Réfléchis un peu. Le jour 7 est le dimanche, alors le jour 8 est le jour suivant le dimanche, donc le lundi, le 1er jour de la semaine ! Et voici ta première addition modulo 7 : \(3+5=8\equiv1\).

Et dans 9 jours ? Et bien, dis-toi que 9 jours c’est une semaine et 2 jours. Dans une semaine nous serons mercredi, 2 jours après nous serons vendredi, le 5e jour de la semaine. Ta deuxième addition modulo 7 : \(3+9=3+(7+2)\equiv3+2=5\)

Et dans un mois ? le 8 février ? Quel jour serons-nous ? Le mois de janvier ayant 31 jours — c’est-à-dire 4 semaines et 3 jours — l’addition s’écrit \(3+31=3+(4\times7+3)\equiv3+3=6\). Le 8 février sera donc le 6e jour de la semaine, c’est-à-dire un samedi.

Et le 8 mars ? Un samedi aussi, car l’année n’est pas bissextile. Vois-tu le rapport ? 28 jours entre le 8 février et le 8 mars et \(6+28=6+(4\times7+0)\equiv6+0=6\).

Quelle est la différence entre \(=\) et \(\equiv\) ? Le deuxième signifie que l’on ne tient pas compte des paquets de 7 qui nous gênent. Ils sont là, mais on les masque. Ainsi, pour parler des mercredis on peut se permettre d’écrire \(3\equiv10\equiv17\equiv24\equiv31\equiv38\equiv…\equiv73\equiv…\).

Un dernier exemple ? Dans un an ? C’est-à-dire dans 365 jours ? 365 divisé par 7 égale, euh, un peu plus de 50 ? 51 ? non, 52. Et oui, il y a 52 semaines dans une année. Mais \(52\times7=364\). Finalement on écrit \(365=7\times52+1\equiv1\). Une année se comporte donc comme une journée. Que le temps passe vite quand on fait des maths 😊 Ainsi, si aujourd’hui est un mercredi, nous serons jeudi dans un an.

Additions et soustraction

Toutes les opérations usuelles ne sont pas compatibles avec les congruences, ce serait trop beau !

Une addition

Quel est le chiffre des unités de \(1234+5678\) ? À l’école tu as appris : “4 et 8 font douze, j’écris 2 et je retiens 1”. En terminale tu écriras plutôt \(4+8=12=1\times10+2\equiv2\).

Mais, mais ? Et 1230 ? Et 5670 ? On les oublie ? Et bien oui, car ce sont des paquets de 10. Tout comme dans le calendrier perpétuel on mettait de côté les paquets de 7. À l’école on travaille sans cesse — et sans le dire— modulo 10. En maths expertes il faudra préciser si tu travailles modulo 10, modulo 7, modulo…

Ainsi, pour répondre à la question ci-dessus, \(1234+5678=(123\times10+4)+(567\times10+8)\equiv4+8=12\equiv2\text{ mod }10\). Le chiffre des unités est donc 2.

Les additions sont compatibles avec les congruences, ouf ! On peut donc essayer d’aller plus loin.

L’opposé

Au collège tu as vu que l’opposé de 1 était -1, l’opposé de 2 était -2, etc Facile, non ? Euh, oui, mais euh, on peut mettre des “moins” devant le numéro des jours ? Si le 3e jour est le mercredi, quel sera le -3e jour ?

Revenons à une définition simple de deux nombres opposés : \(a\text{ et }b\text{ sont opposés ssi }a+b=0\). Déformons-la un peu : \(a\text{ et }b\text{ sont opposés modulo }n\iff a+b\equiv0\text{ mod }n\)

Quel est alors l’opposé du mercredi dans une semaine ? Le jeudi ? oui, très bien, puisque \(3+4=7\equiv0\text{ mod }7\). De même mardi et vendredi sont opposés, comme le sont lundi et samedi. Et dimanche ? Quel est son opposé ? Et bien c’est lui-même, puisque \(7+7=14=2\times7+0\equiv0\text{ mod }7\).

Quel est l’opposé de 1 modulo 10 ? Jusque ici c’était -1. Ce n’est plus le cas ? Si, ou 9, au choix 😊 ou 19, ou -11, ou… car \(-1+1\equiv9+1\equiv19+1\equiv…\equiv0\text{ mod }10\).

Tu as sans doute déjà rencontré ce problème avec le cercle trigonométrique. Un angle droit mesure-t-il 90° ou 450° ? ou -270° ? Ce n’est pas trop grave jusqu’au jour où on demande de tracer un demi angle droit : 90° est “équivalent” à -270° mais 45° n’est pas “équivalent” à -135°. Nous y reviendrons un peu plus loin.

En ce qui te concerne, l’important est de savoir que tous les entiers ont des opposés.

Une soustraction

Quel est le chiffre des unités de \(1234-678\) ? \(4-8=-4\) ? ah ? non ?

Méthode apprise à l’école : \(4-8\equiv14-8=6\)

Avec l’opposé de 8 : \(4-8=4+(-8)\equiv4+2=6\). La soustraction globale s’écrit \(1234-678=(123\times10+4)-(67\times10+8)\equiv4-8\equiv4+2=6\).
Les soustractions et les congruences sont compatibles, continuons !

Multiplications et divisions

Multiplications

As-tu le droit d’écrire \(1234\times678\equiv4\times8=32\equiv2\) ?

Entrons dans les détails et distribuons : \(1234\times678=(123\times10+4)\times(67\times10+8)=(123\times10\times67\times10)+(4\times67\times10)+(123\times8\times10)+4\times8\).

Pour savoir si la congruence est compatible, tu enlèves les paquets de 10. Tu obtiens \(4\times8\), c’est parfait.

Divisions

Que penses-tu de \(14÷2\equiv4÷2=2\text{ mod }10\) ?

Pourquoi ça ne fonctionne pas ?

Ici aussi, entrons dans les détails du calcul : \(14÷2=(10+4)÷2=5+2=7\text{ mod }10\) !

Le paquet de 10 s’est transformé en paquet de 5 ! On ne peut donc plus continuer à écrire modulo 10, il faudra passer à modulo 5. Nous voilà revenus au problème du cercle trigonométrique, où un demi angle droit peut valoir 225° au lieu de 45° si la mesure initiale de l’angle droit était 90°+360°=450°.

L’intérêt de travailler avec des congruences est de grandement simplifier les calculs. Cet intérêt disparait si on doit prendre garde au modulo. On s’interdira donc de faire des divisions dans les congruences, même si elles semblent tomber juste.

Ce qui pose un autre problème : comment résoudre des équations sans divisions ? Je ne peux pas traiter quelque-chose d’aussi simple que \(ax=b\) avec les congruences ? Et bien, ça dépend 🤨😏

Équations \(ax+b\equiv c\text{ mod }n\)

Opposé ou soustraction ?

Je te propose un exemple relativement simple : \(3x+1\equiv7\text{ mod }10\).

pourquoi “simple” ? parce que \(x=2\) est une solution évidente ;
pourquoi “relativement” ? parce que \(x=2\) n’est peut-être pas la seule solution…

Pour simplifier l’équation, vas-tu soustraire 1 ou ajouter l’opposé de 1 ?

par soustraction : \(3x+1\equiv7\iff3x\equiv6\) ;
en ajoutant 9, l’opposé de 1 : \(3x+1\equiv7\iff3x+1+9\equiv7+9\iff3x\equiv6\).
la cause semble entendue, il vaut mieux soustraire ; mais avec l’équation \(3x+8\equiv7\), que ferais-tu ? soustraire 8 ou ajouter 2 ?

Inverse ou division ?

Comme nous nous sommes interdits de faire des divisions quelques lignes plus haut, je te propose de revenir à une phrase bien connue des collégiens : “diviser par une fraction c’est multiplier par son inverse”. Et tu vas alors multiplier l’équation \(3x\equiv6\) par l’inverse de 3.

Pas de fraction dans le cours d’arithmétique, donc interdit d’écrire \({1\over3}\) ! À la rigueur l’inverse de 3 s’écrira \(3^{-1}\) mais en pratique cette notation n’est pas utile et donc pas utilisée.

Mais qu’est-ce que l’inverse ? Les fractions \({3\over5}\) et \({5\over3}\) sont dites “inverses” car on a inversé numérateur et dénominateur. Mais mathématiquement elles sont inverses car leur produit vaut 1. De même l’inverse de 4 est 0,25 car \(4\times0.25=1\).

Avec les congruences, deux entiers \(a\text{ et }b\) sont dits inverses modulo \(n\) lorsque \(a\times b\equiv1\text{ mod }n\).

Ainsi l’inverse de 3 modulo 10 est 7 car \(3\times7=21\equiv1{ mod }10\). J’ai écrit “l’inverse” alors que “un des inverses” serait plus juste. 17 est également inverse de 3, mais aussi 27, ou -3, -13 etc.

Revenons à l’équation : \(3x\equiv6\iff7\times3x\equiv7\times6\iff1x\equiv42\iff x\equiv2\text{ mod }10\)

Conclusion : x est égal à 2, ou à 12, ou à 22, ou à -8, à -18 etc.

Tout ça pour ça ?

Je t’entends déjà dire “ben moi j’ai divisé \(3x\equiv6\) par 3 et j’ai trouvé \(x\equiv2\) sans tout ça ! et ça va plus vite !”

Oui, oui, mais… écrirais-tu \(2x\equiv6\iff x\equiv3\) ? Oui, sans doute. Mais ce qui était correct avec 3 devient faux avec 2, en tout cas modulo 10. Tu aurais oublié la solution \(x\equiv8\).

Pourquoi ça marche avec 3 et pas avec 2 ? Parce que 3 est inversible modulo 10, et pas 2. Ou, pour le dire autrement, parce que 3 est premier avec 10, et pas 2.

Et comment résoudre \(3x\equiv8\) avec ta méthode ?

rechercher un multiple de 3 se terminant par 8 : 18
\(3x\equiv8\iff3x\equiv18\) donne \(x\equiv6\)
justifier qu’il n’y a pas d’autre solution car 3 est premier avec 10 et que … théorème de Gauss …

Bon, pas très rentable. Rien que la première étape — rechercher un multiple de 3 qui se termine par 8 — est aussi longue que chercher l’inverse de 3 — un multiple de 3 qui se termine par 1.

Et sans l’inverse ?

La méthode de l’inverse est très efficace, elle te sera également utile dans le cours sur les matrices.

Néanmoins tous les entiers ne sont pas inversibles. 0, 2, 4, 5, 6, 8 n’ont pas d’inverse modulo 10 car un multiple d’un nombre pair ne peut pas se terminer par 1. Même chose avec un multiple de 5.

Il existe une autre méthode : le tableau de valeurs. x prend toutes les valeurs entières de 0 à n-1 — donc de 0 à 9 si tu travailles modulo 10.

Un exemple modulo 9 :

Méthode longue et un peu fastidieuse, mais qui fonctionne très bien, tant que tu t’en tiens aux opérations déjà rencontrées : additions, soustractions, multiplications.

\(5\times2=10=9+1\equiv1\text{ mod }9\)
\(5\times3=15=9+6\equiv6\text{ mod }9\)
\(5\times4=20=2\times9+2\equiv2\text{ mod }9\)

Tu peux aller plus vite en comptant de 5 en 5: 0, 5, 10, 15, 20. Vraiment mieux ? Oui, si tu utilises l’opposé de 5, c’est-à-dire 4 car \(5+4=9\equiv0\text{ mod }9\). En effet ajouter 5, c’est soustraire son opposé 4 :