arithmétique modulaire

Discipline

arithmétique opérant sur l'anneau des entiers relatifs, permettant la résolution de problèmes sur les nombres entiers

domaine: Arithmétique · Mathématiques

Pour comprendre

L’arithmétique modulaire est une arithmétique opérant sur l’anneau des entiers relatifs. Elle permet de traiter des problèmes portant sur les nombres entiers en regardant notamment les restes obtenus dans une division.

Ce qu'elle étudie

Dans ce cadre, deux entiers peuvent être considérés ensemble lorsqu’ils ont le même reste dans la division par un entier donné. L’écriture de congruence exprime cette relation entre $a$ et $b$. L’arithmétique modulaire donne ainsi une manière de reformuler certains problèmes sur les nombres entiers à partir des restes de division. Elle reste une arithmétique des entiers relatifs, orientée vers la résolution de ces problèmes.

$$a \equiv b \pmod{n}$$

Cette formule signifie que $a$ et $b$ ont le même reste dans la division par $n$.

À quoi elle sert

Elle sert à résoudre des problèmes sur les nombres entiers en utilisant les relations entre restes de division.

Comparer des entiers qui ont le même reste.
Exprimer une congruence entre deux entiers.
Reformuler des problèmes de nombres entiers dans l’anneau des entiers relatifs.

Où elle se place

L’arithmétique modulaire est une branche des mathématiques et de l’arithmétique. Le diagramme la place parmi d’autres branches des mathématiques.

flowchart TD
  P0[Mathématiques] --> D([arithmétique modulaire])
  P1[Arithmétique] --> D([arithmétique modulaire])
  P0 --> S0[algebre]
  P0 --> S1[analyse]
  P0 --> S2[arithmetique]
  P0 --> S3[combinatoire]

Le cycle des restes

Cette figure montre le reste de la division de $x$ par 5 : la courbe monte de 0 à 5, retombe, et recommence indéfiniment. C'est le cycle des restes, celui de l'horloge et des calendriers. Cette répétition régulière est l'objet même de l'arithmétique modulaire.

{ "boundingBox": [ -1, 6.5, 16, -1.2 ], "axis": true, "grid": true, "functions": [ { "expression": "x-5*floor(x/5)", "range": [ 0, 15.5 ], "color": "#2563eb", "width": 2, "label": "reste de x modulo 5" } ] }

Cas d’usage

Regardons où sera l'aiguille d'une horloge dans cinq heures, s'il est neuf heures maintenant. On additionne :

$$9+5=14$$

Le cadran recommence après douze heures. On retire donc un tour complet : $14-12=2$. Cela s'écrit :

$$14\equiv2\pmod{12}$$

Le signe $\equiv$ indique ici que les nombres donnent la même position sur le cadran. L'aiguille sera sur le $2$.

Cherchons ensuite quel jour tombera cent jours après un lundi. Les jours reviennent par semaines de sept jours. La division donne :

$$100=14\times7+2$$

$$100\equiv2\pmod{7}$$

Les quatorze semaines complètes ramènent à un lundi. Il reste deux jours à avancer : on arrive un mercredi.

Trouvons enfin le dernier chiffre de $7^{100}$. Pour cela, il suffit de garder les restes de la division par dix. Calculons les premières puissances utiles :

$$7^2=49\equiv9\pmod{10}$$

$$7^3\equiv9\times7\equiv3\pmod{10}$$

$$7^4=2\,401\equiv1\pmod{10}$$

Un groupe de quatre facteurs $7$ a donc pour reste $1$. Or $100=4\times25$ : on peut regrouper les facteurs par quatre.

$$7^{100}=(7^4)^{25}\equiv1^{25}=1\pmod{10}$$

Chaque groupe se remplace par son reste, et multiplier des $1$ donne encore $1$. Le dernier chiffre est donc $1$, sans écrire ce nombre de 85 chiffres.

Sources

Wikidata CC0-1.0

wikidata Q319400