Arithmétique et Z/nZ : cours de maths en L2 en PDF.

Une relation binaire \(\mathcal{R}\) sur un ensemble \(E\) est une relation d’équivalence si elle est :

• réflexive : \(\forall x \in E,\ x \mathcal{R} x\) ;
• symétrique : \(\forall x, y \in E,\ x \mathcal{R} y \Rightarrow y \mathcal{R} x\) ;
• transitive : \(\forall x, y, z \in E,\ (x \mathcal{R} y \text{ et } y \mathcal{R} z) \Rightarrow x \mathcal{R} z\).

La classe de \(x\) est \(\overline{x} = \{y \in E \mid x \mathcal{R} y\}\). L’ensemble quotient \(E/\mathcal{R}\) est l’ensemble de toutes les classes.

Les classes d’équivalence forment une partition de \(E\) : elles sont non vides, leur réunion vaut \(E\), et deux classes sont soit égales, soit disjointes. De plus, \(\overline{x} = \overline{y} \Leftrightarrow x \mathcal{R} y\).

D’abord, par réflexivité, \(x \in \overline{x}\), donc chaque classe est non vide et la réunion des classes vaut \(E\). Ensuite, supposons \(x \mathcal{R} y\). Si \(z \in \overline{y}\), alors \(y \mathcal{R} z\), donc \(x \mathcal{R} z\) par transitivité, et \(z \in \overline{x}\). Ainsi \(\overline{y} \subset \overline{x}\), et l’inclusion inverse vient de la symétrie. Enfin, si \(z \in \overline{x} \cap \overline{y}\), alors \(x \mathcal{R} z\) et \(y \mathcal{R} z\), donc \(x \mathcal{R} y\) et \(\overline{x} = \overline{y}\). Deux classes qui se rencontrent sont donc égales.

Définir une application sur \(E/\mathcal{R}\) par une formule en \(x\) exige de vérifier que le résultat ne dépend pas du représentant choisi. On dit alors que l’application est bien définie. Par exemple, sur \(\mathbb{Z}/3\mathbb{Z}\), la formule \(\overline{x} \mapsto \overline{2^x}\) n’a pas de sens : \(\overline{0} = \overline{3}\), mais \(2^0 = 1\) et \(2^3 = 8 \equiv 2 \pmod 3\).

Sur \(\mathbb{R}\), posons \(x \sim y \Leftrightarrow x – y \in \mathbb{Z}\). C’est une relation d’équivalence, car \(\mathbb{Z}\) contient \(0\), est stable par opposé et par somme. Chaque classe contient exactement un réel de \([0, 1[\), à savoir la partie fractionnaire. Autrement dit, \(\mathbb{R}/\mathbb{Z}\) s’identifie à \([0,1[\), c’est-à-dire à un cercle.

Deux entiers \(a\) et \(b\) sont congrus modulo \(n\) si \(n\) divise \(b – a\). On note \(a \equiv b \pmod n\). De façon équivalente, \(a\) et \(b\) ont le même reste dans la division euclidienne par \(n\).

La congruence est compatible avec l’addition et la multiplication : si \(a \equiv a^{\prime} \pmod n\) et \(b \equiv b^{\prime} \pmod n\), alors

\[a + b \equiv a^{\prime} + b^{\prime} \pmod n \quad \text{et} \quad ab \equiv a^{\prime} b^{\prime} \pmod n.\]

Par récurrence, \(a^k \equiv (a^{\prime})^k \pmod n\) pour tout \(k \in \mathbb{N}\).

Écrivons \(a^{\prime} = a + un\) et \(b^{\prime} = b + vn\). Alors \(a^{\prime} + b^{\prime} = a + b + (u+v)n\). De plus, \(a^{\prime} b^{\prime} = ab + (av + bu + uvn)n\). Les deux différences sont donc des multiples de \(n\).

Comme \(10 \equiv 1 \pmod 9\), on a \(10^k \equiv 1 \pmod 9\) pour tout \(k\). Par conséquent, un entier est congru à la somme de ses chiffres modulo \(9\). De même, \(10 \equiv -1 \pmod{11}\) : un entier est congru modulo \(11\) à la somme alternée de ses chiffres, en partant des unités.

On ne simplifie pas librement une congruence. Par exemple, \(2 \times 3 \equiv 2 \times 0 \pmod 6\), mais \(3 \not\equiv 0 \pmod 6\). La simplification par \(c\) n’est permise que si \(c\) est premier avec \(n\).

Les formules \(\overline{a} + \overline{b} = \overline{a+b}\) et \(\overline{a} \times \overline{b} = \overline{ab}\) définissent bien deux lois sur \(\mathbb{Z}/n\mathbb{Z}\). Muni de ces lois, \(\mathbb{Z}/n\mathbb{Z}\) est un anneau commutatif, de zéro \(\overline{0}\) et d’unité \(\overline{1}\). De plus, la projection \(\pi : \mathbb{Z} \to \mathbb{Z}/n\mathbb{Z}\) est un morphisme d’anneaux surjectif, de noyau \(n\mathbb{Z}\).

D’abord, les lois sont bien définies : si \(\overline{a} = \overline{a^{\prime}}\) et \(\overline{b} = \overline{b^{\prime}}\), la proposition de compatibilité donne \(\overline{a+b} = \overline{a^{\prime}+b^{\prime}}\) et \(\overline{ab} = \overline{a^{\prime}b^{\prime}}\). Ensuite, chaque axiome d’anneau se transporte depuis \(\mathbb{Z}\). Par exemple, pour la distributivité :

\[\overline{a}(\overline{b} + \overline{c}) = \overline{a(b+c)} = \overline{ab + ac} = \overline{a}\,\overline{b} + \overline{a}\,\overline{c}.\]

Enfin, \(\pi(a+b) = \pi(a) + \pi(b)\) et \(\pi(ab) = \pi(a)\pi(b)\) par définition des lois. Son noyau est \(\{a \mid \overline{a} = \overline{0}\} = n\mathbb{Z}\).

Pour \(a \in \mathbb{Z}\), la classe \(\overline{a}\) est inversible dans \(\mathbb{Z}/n\mathbb{Z}\) si et seulement si \(\operatorname{pgcd}(a, n) = 1\).

Supposons \(\overline{a}\,\overline{u} = \overline{1}\). Il existe alors \(v \in \mathbb{Z}\) tel que \(au – 1 = vn\), soit \(au – vn = 1\). Tout diviseur commun à \(a\) et \(n\) divise donc \(1\). Réciproquement, si \(\operatorname{pgcd}(a,n) = 1\), le théorème de Bézout fournit \(u, v\) avec \(au + nv = 1\). En passant aux classes, \(\overline{a}\,\overline{u} = \overline{1}\).

Pour inverser \(\overline{a}\) modulo \(n\) :

1. on applique l’algorithme d’Euclide à \(n\) et \(a\) jusqu’au reste \(1\) ;
2. on remonte les divisions pour écrire \(1 = au + nv\) ;
3. on conclut : \(\overline{a}^{-1} = \overline{u}\), qu’on ramène dans \(\{0, \ldots, n-1\}\) ;
4. on vérifie en calculant \(au\) modulo \(n\).

Inversons \(17\) modulo \(60\). D’abord, \(60 = 3 \times 17 + 9\), puis \(17 = 9 + 8\) et \(9 = 8 + 1\). En remontant :

\[1 = 9 – 8 = 2 \times 9 – 17 = 2 \times 60 – 7 \times 17.\]

Donc \(\overline{17}^{-1} = \overline{-7} = \overline{53}\). En effet, \(17 \times 53 = 901 = 15 \times 60 + 1\).

Soient \(a, b \in \mathbb{Z}\) et \(d = \operatorname{pgcd}(a, n)\). L’équation \(\overline{a}\,x = \overline{b}\) admet une solution dans \(\mathbb{Z}/n\mathbb{Z}\) si et seulement si \(d \mid b\). Dans ce cas, elle en admet exactement \(d\), qui forment une seule classe modulo \(n/d\).

Si \(ax = b + kn\), alors \(d\) divise \(ax – kn = b\). Réciproquement, si \(d \mid b\), écrivons \(a = da_1\), \(b = db_1\), \(n = dn_1\) avec \(\operatorname{pgcd}(a_1, n_1) = 1\). Alors \(n \mid ax – b\) équivaut à \(n_1 \mid a_1 x – b_1\). Autrement dit, \(x \equiv a_1^{-1} b_1 \pmod{n_1}\), où l’inverse est pris modulo \(n_1\). Cette classe modulo \(n_1\) contient exactement \(d\) classes modulo \(n\).

Soit \(n \geq\, 2\). L’anneau \(\mathbb{Z}/n\mathbb{Z}\) est un corps si et seulement si \(n\) est premier. Il est alors noté \(\mathbb{F}_p\) lorsque \(n = p\).

Si \(p\) est premier et \(p \nmid a\), alors \(\operatorname{pgcd}(a, p) = 1\). Par conséquent, toute classe non nulle est inversible. Réciproquement, si \(n = rs\) avec \(1 < r, s < n\), alors \(\overline{r}\,\overline{s} = \overline{0}\) avec \(\overline{r} \neq \overline{0}\) et \(\overline{s} \neq \overline{0}\). L’anneau n’est donc pas intègre, et ce n’est pas un corps.

L’indicatrice d’Euler de \(n \geq\, 1\) est \(\varphi(n) = \operatorname{card}\{k \in \{1, \ldots, n\} \mid \operatorname{pgcd}(k, n) = 1\}\). D’après la partie III, c’est le cardinal du groupe \((\mathbb{Z}/n\mathbb{Z})^{\times }\).

Si \(p\) est premier et \(k \geq\, 1\), alors \(\varphi(p^k) = p^k – p^{k-1}\). Si \(\operatorname{pgcd}(m, n) = 1\), alors \(\varphi(mn) = \varphi(m)\varphi(n)\). Par suite, si \(n = p_1^{k_1} \cdots p_r^{k_r}\),

\[\varphi(n) = n \prod_{i=1}^{r} (1 – \frac{1}{p_i}).\]

On a \(360 = 2^3 \times 3^2 \times 5\). Donc \(\varphi(360) = 360 \times \frac{1}{2} \times \frac{2}{3} \times \frac{4}{5} = 96\).

(Théorème d’Euler) Si \(\operatorname{pgcd}(a, n) = 1\), alors \(a^{\varphi(n)} \equiv 1 \pmod n\).

Notons \(G = (\mathbb{Z}/n\mathbb{Z})^{\times }\) et \(\alpha = \overline{a} \in G\). L’application \(x \mapsto \alpha x\) est une bijection de \(G\) dans \(G\), de réciproque \(x \mapsto \alpha^{-1}x\). Par conséquent, le produit de tous les éléments de \(G\) ne change pas :

\[\prod_{x \in G} x = \prod_{x \in G} (\alpha x) = \alpha^{\varphi(n)} \prod_{x \in G} x.\]

Le produit étant inversible, on le simplifie. Il reste \(\alpha^{\varphi(n)} = \overline{1}\).

(Petit théorème de Fermat) Soit \(p\) premier. Si \(p \nmid a\), alors \(a^{p-1} \equiv 1 \pmod p\). Pour tout \(a \in \mathbb{Z}\), on a \(a^p \equiv a \pmod p\).

La réciproque du petit théorème de Fermat est fausse. Par exemple, \(2^{10} = 1024 = 3 \times 341 + 1\), donc \(2^{340} \equiv 1 \pmod{341}\), alors que \(341 = 11 \times 31\) n’est pas premier.

Pour calculer \(a^k\) modulo \(n\) :

1. si \(\operatorname{pgcd}(a, n) = 1\), on réduit l’exposant modulo \(\varphi(n)\) (ou modulo un exposant \(m\) connu tel que \(a^m \equiv 1\)) ;
2. on écrit l’exposant restant en base \(2\) ;
3. on calcule les carrés successifs \(a, a^2, a^4, a^8, \ldots\), chacun réduit modulo \(n\) ;
4. on multiplie les carrés qui correspondent aux chiffres \(1\) de l’écriture binaire.

Cette exponentiation rapide demande de l’ordre de \(2\log_2 k\) multiplications, au lieu de \(k – 1\).

Calculons \(3^{2026}\) modulo \(1000\). Comme \(\varphi(1000) = 400\) et \(2026 = 5 \times 400 + 26\), on a \(3^{2026} \equiv 3^{26}\). Ensuite, \(3^{10} = 59049 \equiv 49\), donc \(3^{20} \equiv 49^2 = 2401 \equiv 401\). Enfin, \(3^{26} \equiv 401 \times 729 = 292329 \equiv 329 \pmod{1000}\).

(Théorème chinois) Soient \(m, n \geq\, 1\) premiers entre eux. L’application

\[\psi : \mathbb{Z}/mn\mathbb{Z} \to \mathbb{Z}/m\mathbb{Z} \times \mathbb{Z}/n\mathbb{Z}, \qquad x \bmod mn \mapsto (x \bmod m,\ x \bmod n)\]

est bien définie, et c’est un isomorphisme d’anneaux. En particulier, pour tous \(a, b\), le système \(x \equiv a \pmod m\), \(x \equiv b \pmod n\) a une unique solution modulo \(mn\).

D’abord, \(\psi\) est bien définie : si \(x \equiv x^{\prime} \pmod{mn}\), alors \(x \equiv x^{\prime}\) modulo \(m\) et modulo \(n\). C’est un morphisme d’anneaux, car les lois se calculent sur les représentants. Ensuite, si \(\psi(\overline{x}) = (0, 0)\), alors \(m \mid x\) et \(n \mid x\). Comme \(m\) et \(n\) sont premiers entre eux, \(mn \mid x\) par le lemme de Gauss. Ainsi \(\psi\) est injective. Enfin, les deux ensembles ont \(mn\) éléments, donc \(\psi\) est bijective.

Pour résoudre \(x \equiv a \pmod m\), \(x \equiv b \pmod n\) avec \(\operatorname{pgcd}(m, n) = 1\) :

1. on trouve par Bézout \(u, v\) tels que \(mu + nv = 1\) ;
2. on pose \(x_0 = b\,mu + a\,nv\) : en effet \(nv \equiv 1 \pmod m\) et \(mu \equiv 1 \pmod n\) ;
3. les solutions sont les \(x_0 + kmn\), \(k \in \mathbb{Z}\).

Avec plus de deux modules deux à deux premiers entre eux, on procède de même, ou bien on fusionne les équations deux par deux.

Résolvons \(x \equiv 2 \pmod 3\) et \(x \equiv 3 \pmod 5\). On a \(3 \times 2 + 5 \times (-1) = 1\). Donc \(x_0 = 3 \times 6 + 2 \times (-5) = 8\). Vérification : \(8 = 2 \times 3 + 2\) et \(8 = 5 + 3\). Les solutions sont les \(8 + 15k\).

Si \(\operatorname{pgcd}(m, n) = 1\), alors \(\psi\) induit un isomorphisme de groupes \((\mathbb{Z}/mn\mathbb{Z})^{\times } \simeq (\mathbb{Z}/m\mathbb{Z})^{\times } \times (\mathbb{Z}/n\mathbb{Z})^{\times }\). Par conséquent, \(\varphi(mn) = \varphi(m)\varphi(n)\).

Si \(d = \operatorname{pgcd}(m, n) > 1\), le système a des solutions si et seulement si \(a \equiv b \pmod d\). Dans ce cas, elles forment une seule classe modulo \(\operatorname{ppcm}(m, n)\).

L’application \(x \mapsto x^2\) de \(\mathbb{F}_p^{\times }\) dans lui-même est exactement « deux pour un ». Par conséquent, \(\mathbb{F}_p^{\times }\) contient exactement \(\frac{p-1}{2}\) carrés.

Si \(x^2 = y^2\), alors \((x-y)(x+y) = 0\). Comme \(\mathbb{F}_p\) est un corps, donc intègre, on obtient \(y = x\) ou \(y = -x\). De plus, \(x \neq -x\) car \(2x \neq 0\) lorsque \(p\) est impair. Chaque carré non nul a donc exactement deux racines. Ainsi, les \(p – 1\) éléments de \(\mathbb{F}_p^{\times }\) fournissent \(\frac{p-1}{2}\) carrés.

(Critère d’Euler) Soit \(a \in \mathbb{F}_p^{\times }\). Alors \(a^{\frac{p-1}{2}} = 1\) si \(a\) est un carré, et \(a^{\frac{p-1}{2}} = -1\) sinon.

Posons \(b = a^{\frac{p-1}{2}}\). D’après Fermat, \(b^2 = a^{p-1} = 1\), donc \(b = \pm 1\). Si \(a = x^2\), alors \(b = x^{p-1} = 1\). Ainsi, les \(\frac{p-1}{2}\) carrés sont racines du polynôme \(X^{\frac{p-1}{2}} – 1\). Or ce polynôme, sur le corps \(\mathbb{F}_p\), a au plus \(\frac{p-1}{2}\) racines. Ses racines sont donc exactement les carrés. Par conséquent, un non-carré vérifie \(b \neq 1\), c’est-à-dire \(b = -1\).

Le critère donne aussitôt : \(-1\) est un carré de \(\mathbb{F}_p\) si et seulement si \((-1)^{\frac{p-1}{2}} = 1\), soit \(p \equiv 1 \pmod 4\). Ainsi \(-1\) est un carré modulo \(13\), car \(5^2 = 25 \equiv -1\). En revanche, ce n’est pas un carré modulo \(7\).

Le destinataire choisit deux grands nombres premiers distincts \(p\) et \(q\), et pose \(n = pq\). Ensuite, il choisit \(e\) premier avec \(\varphi(n) = (p-1)(q-1)\) et calcule \(d\) tel que \(ed \equiv 1 \pmod{\varphi(n)}\). La clé publique est \((n, e)\) ; la clé privée est \(d\).

• Chiffrement d’un message \(m \in \{0, \ldots, n-1\}\) : \(c = m^e \bmod n\).
• Déchiffrement : \(m = c^d \bmod n\).

Avec les notations précédentes, \(m^{ed} \equiv m \pmod n\) pour tout entier \(m\).

Écrivons \(ed = 1 + k(p-1)(q-1)\) avec \(k \in \mathbb{N}\). Travaillons d’abord modulo \(p\). Si \(p \mid m\), les deux membres sont nuls. Sinon, Fermat donne \(m^{p-1} \equiv 1\), donc \(m^{ed} = m (m^{p-1})^{k(q-1)} \equiv m \pmod p\). De même, \(m^{ed} \equiv m \pmod q\). Enfin, \(p\) et \(q\) sont premiers entre eux : le théorème chinois donne \(m^{ed} \equiv m \pmod{pq}\).

Prenons \(p = 5\), \(q = 11\), donc \(n = 55\) et \(\varphi(n) = 40\). Avec \(e = 3\), on trouve \(d = 27\), car \(81 = 2 \times 40 + 1\). Le message \(m = 7\) se chiffre en \(7^3 = 343 \equiv 13 \pmod{55}\). Le déchiffrement \(13^{27} \bmod 55\) redonne bien \(7\).

Connaître \(\varphi(n)\) revient à connaître \(p\) et \(q\). En effet, \(p + q = n – \varphi(n) + 1\) et \(pq = n\) : ce sont les racines d’un trinôme. C’est pourquoi \(\varphi(n)\) doit rester secret. En pratique, \(p\) et \(q\) ont plusieurs centaines de chiffres.