Ivan Shishkin, Birch Grove

Congruence modulo nn

Concept history

A revision trail for this concept page.

4 revisions

Back

Revision 3147

8/31/2026, 1:52:40 PM · visitor

Concept marked usable

statusStubUsable

Revision 3146

8/31/2026, 1:52:32 PM · visitor

Updated title, language, text and aliases

titleCongruence modulo nCongruence modulo nn
languageEnglishFrançais
aliasesNoneCongruence
Compare with revision 51331 changed lines
1##### Définition intuitive
2La congruence modulo $n$ consiste à ne retenir des entiers que leur reste dans la division par $n$, en oubliant délibérément le quotient. C'est l'arithmétique de l'horloge (numérique) : trois heures après vingt-trois heures, il est deux heures, parce qu'on travaille modulo $24$.
1
4##### Définition formelle
5Soit $n\in\mathbb{N}^{*}$. Deux entiers $a,b\in\mathbb{Z}$ sont dits *congrus modulo $n$*, ce qu'on note
6$$a\equiv b \pmod n,$$
7si $n$ divise $b-a$, c'est-à-dire s'il existe $k\in\mathbb{Z}$ tel que $b=a+kn$.
8
9**Proposition.** C'est une relation d'équivalence sur $\mathbb{Z}$, compatible avec l'addition et la multiplication :
10$$a\equiv a' \text{ et } b\equiv b'\ \Longrightarrow\ a+b\equiv a'+b'\quad\text{et}\quad ab\equiv a'b' \pmod n .$$
11
12*Preuve de la compatibilité multiplicative.* Si $a'=a+kn$ et $b'=b+\ell n$, alors $a'b'=ab+n(a\ell+bk+k\ell n)$. $\square$
13
14L'ensemble quotient, noté $\mathbb{Z}/n\mathbb{Z}$, hérite donc d'une structure d'**anneau commutatif** ; il possède exactement $n$ éléments, les classes $\overline{0},\overline{1},\dots,\overline{n-1}$, car la division euclidienne assure que tout entier est congru à un unique reste dans $\llbracket 0,n-1\rrbracket$.
15
16**Inversibilité.** La classe $\overline{a}$ est inversible dans $\mathbb{Z}/n\mathbb{Z}$ si et seulement si $\mathrm{pgcd}(a,n)=1$. En effet, l'identité de Bézout $au+nv=1$ fournit $\overline{a}\,\overline{u}=\overline{1}$ ; réciproquement, $au\equiv 1$ signifie $au-1=kn$, donc tout diviseur commun de $a$ et $n$ divise $1$. Le groupe des inversibles $(\mathbb{Z}/n\mathbb{Z})^{\times}$ est ainsi d'ordre $\varphi(n)$, et
17$$\mathbb{Z}/n\mathbb{Z} \text{ est un corps}\iff n \text{ est premier}.$$
18
19##### Remarques
20* **Simplification interdite.** On ne peut pas diviser librement : $2\cdot 3\equiv 2\cdot 0 \pmod 6$ sans que $3\equiv 0$. La règle exacte est $ac\equiv bc\pmod n\iff a\equiv b\pmod{n/\mathrm{pgcd}(c,n)}$ ; la simplification par $c$ n'est valide que si $\mathrm{pgcd}(c,n)=1$.
21* **Fermat et Euler.** Le théorème de Lagrange appliqué à $(\mathbb{Z}/n\mathbb{Z})^{\times}$ donne $a^{\varphi(n)}\equiv 1\pmod n$ dès que $\mathrm{pgcd}(a,n)=1$ ; pour $n=p$ premier, on retrouve $a^{p-1}\equiv 1$ et, sans condition, $a^{p}\equiv a\pmod p$.
22* **Théorème des restes chinois.** Si $\mathrm{pgcd}(m,n)=1$, l'application naturelle $\mathbb{Z}/mn\mathbb{Z}\to\mathbb{Z}/m\mathbb{Z}\times\mathbb{Z}/n\mathbb{Z}$ est un isomorphisme d'anneaux. Un système de congruences à modules premiers entre eux a donc toujours une solution, unique modulo le produit. On en déduit la multiplicativité de $\varphi$.
23* **Équations linéaires.** L'équation $ax\equiv b\pmod n$ admet une solution si et seulement si $d=\mathrm{pgcd}(a,n)$ divise $b$, auquel cas elle en a exactement $d$ modulo $n$. C'est la traduction modulaire du théorème de Bézout.
24* **Structure du groupe des inversibles.** $(\mathbb{Z}/n\mathbb{Z})^{\times}$ est cyclique si et seulement si $n\in\{1,2,4,p^{k},2p^{k}\}$ avec $p$ premier impair. Un générateur s'appelle alors une *racine primitive* modulo $n$. En particulier $(\mathbb{Z}/8\mathbb{Z})^{\times}\simeq(\mathbb{Z}/2\mathbb{Z})^{2}$ n'est pas cyclique.
25
26
27##### Exemples
281. **Horloge (à aiguilles).** Modulo $12$, on a $23\equiv 11$ et $15+9\equiv 0$. Modulo $7$, les jours de la semaine : si aujourd'hui est un lundi, dans $100$ jours ce sera un mercredi, car $100\equiv 2\pmod 7$.
292. **Carrés.** Modulo $4$, un carré vaut $0$ ou $1$ ; modulo $8$, il vaut $0$, $1$ ou $4$. Il en résulte que $n\equiv 3\pmod 4$ n'est jamais somme de deux carrés, et que $x^{2}+y^{2}=3z^{2}$ n'a pas de solution entière non triviale.
303. **Grandes puissances.** Pour calculer $7^{100}\bmod 13$ : le petit théorème de Fermat donne $7^{12}\equiv 1$, et $100=8\cdot 12+4$, donc $7^{100}\equiv 7^{4}=2401\equiv 9\pmod{13}$.
314. **Restes chinois.** Le système $x\equiv 2\pmod 3$, $x\equiv 3\pmod 5$, $x\equiv 2\pmod 7$ a pour unique solution $x\equiv 23\pmod{105}$ — c'est l'énoncé du *Sunzi Suanjing*, du IIIᵉ siècle.
325. **Cryptographie.** Le système RSA repose sur $m^{ed}\equiv m\pmod{N}$ avec $N=pq$ et $ed\equiv 1\pmod{\varphi(N)}$ : chiffrer et déchiffrer sont deux exponentiations modulaires, et la sécurité tient à la difficulté de factoriser $N$.

Revision 513

7/20/2026, 3:46:40 PM · Ancient Tree

Concept edited

This older revision predates detailed metadata tracking.

Revision 512

7/20/2026, 3:46:32 PM · Ancient Tree

Concept created