Anneaux des entiers modulo

On construit l’anneau $\mathbf{Z}/n\mathbf{Z}$.

Sous-groupes additifs du groupe des entiers

La distributivité de la multiplication par rapport à l’addition assure que, pour tout $d\in\mathbf{Z}$, la fonction $n\mapsto dn$ est un endomorphisme du groupe $(\mathbf{Z},+)$. L’image $d\mathbf{Z}=\{dn\mid n\in\mathbf{Z}\}$ de cet endomorphisme est donc un sous-groupe additif de $\mathbf{Z}$.

Lemme. Le sous-groupe $d\mathbf{Z}$ est un idéal de l’anneau $\mathbf{Z}$.

En effet, pour tout $dn\in d\mathbf{Z}$ et tout $a\in\mathbf{Z}$, $(dn)a=d(na)\in d\mathbf{Z}$.

De plus:

Lemme. Pour tout sous-groupe $G$ de $\mathbf{Z}$ tel que $d\in G$, on a $d\mathbf{Z}\subseteq G$.

En effet: on montre par récurrence sur $n\in\mathbf{N}$ que $dn\in G$; et si $n<0$, alors $dn=-d(-n)$.

En fait, tout sous-groupe additif de $\mathbf{Z}$ est de la forme $d\mathbf{Z}$. En effet, si $G$ est un tel sous-groupe additif, alors ou bien $G=\{0\}=0\mathbf{Z}$, ou bien $G$ contient un élément $a\not=0$, et donc aussi $-a$, et donc $G\cap\mathbf{N}^\bullet\not=\emptyset$. Dans ce cas, on pose $d$ le minimum de $G\cap\mathbf{N}^\bullet$ (pour rappel, c’est une forme de récurrence) et on montre que $G=d\mathbf{Z}$. Le dernier lemme ci-dessus donne l’inclusion $G\supseteq d\mathbf{Z}$. Pour l’inclusion réciproque, pour $a\in G$, on écrit la division euclidienne $a=qd+r$ avec $0\le r<d$: on a nécessairement $r=a-qd\in G$, et donc $r=0$ par minimalité de $d$.

On obtient:

Théorème. Les sous-groupes additifs de $\mathbf{Z}$ sont les idéaux $d\mathbf{Z}$ pour $d\in\mathbf{N}$.

Exercices

• Démontrez ou redémontrez le lemme de Bézout:

Lemme. Pour tous $a,b\in\mathbf{Z}$, il existe des entiers $k,l\in\mathbf{Z}$ tels que $ak+bl = a\wedge b$.

• Déduisez-en la variante suivante du théorème de Bachet-Bézout:

Lemme. Pour tous $a,b,c\in\mathbf{Z}$, il existe des entiers $k,l\in\mathbf{Z}$ tels que $ak+bl = c$ ssi $a\wedge b \mid c$.

• Et enfin, tirez-en l’identité $a\mathbf{Z}+b\mathbf{Z}=(a\wedge b)\mathbf{Z}$.

Les groupes cycliques des entiers modulo

Pour tout $n\in\mathbf{N}^\bullet$, la congruence modulo $n$ comme la relation binaire sur $\mathbf{Z}$ définie par $a \equiv b [n]$ ssi $a\mod n = b\mod n$: c’est trivialement une relation d’équivalence. Notons $\bar a_n$ la classe de $a\in\mathbf{Z}$ pour cette équivalence. On peut reformuler: $\bar a_n\equiv\bar b_n$ ssi $n\mid b-a$, c’est-à-dire $b-a\in n\mathbf{Z}$.

On définit alors $\mathbf{Z}/n\mathbf{Z}$ comme le quotient de $\mathbf{Z}$ par cette équivalence. C’est la construction standard du quotient d’un groupe par un sous-groupe normal (ici le groupe est commutatif donc cette hypothèse est automatiquement satisfaite), vue dans le cours de théorie des groupes. On va donc démontrer « à la main » que l’addition dans $\mathbf{Z}$ induit une structure de groupe sur $\mathbf{Z}/n\mathbf{Z}$.

Exercices

• Vérifiez que si $a_0 \equiv a_1 [n]$ et $b_0 \equiv b_1 [n]$ alors $a_0+b_0 \equiv a_1+b_1 [n]$. On peut donc poser $\bar a_n +\bar b_n = \overline{(a+b)}_n$.
• Vérifiez que l’opération précédente définit une loi de groupe.

Réalisation en Python

On propose de représenter les classes de congruence en Python comme suit :

class ZZ():
    
    """Classe pour représenter les éléments des groupes cycliques:
    `ZZ(n,a)` représente la classe de `a` modulo `n`."""
    
    def __init__(self, n, a):
        """Si `a` est un entier relatif et `n` un naturel non nul,
        construit la classe modulo `n` représentée par `a`."""
        if not(isinstance(a,int) and isinstance(n,int) and n > 0):
            raise ValueError("ZZ() attend un entier relatif et un entier naturel non nul")
        self.a = a
        self.n = n

    def injecte(self,a):
        """Si `a` est un entier relatif, renvoie sa classe modulo `self.n`.
        Si c’est déjà une classe modulo `self.n`, la retourne directement.
        Plante sinon."""
        if isinstance(a,int):
            return ZZ(self.n,a)
        if isinstance(a,type(self)) and self.n == a.n:
            return a
        raise ValueError("erreur de conversion")

    def __eq__(self, x):
        """Teste si l’objet courant est égal à l’objet `x`."""
        x = self.injecte(x)
        return (self.a - x.a) % self.n == 0

    def __repr__(self):
        """Retourne une chaîne représentant l’objet courant."""
        return f"ZZ({self.n},{self.a})"
    
    def __str__(self):
        """Retourne une version plus lisible de l’objet courant."""
        return f"{self.a}~n"
    
    def __add__(self,x):
        """Retourne la somme des classes `self` et `x`."""
        x = self.injecte(x)
        return ZZ(self.n,self.a+x.a)

L’idée est de représenter $\bar a_n$ par le couple $(n,a)$, et d’assurer la congruence dans le test d’égalité __eq__() (comme on l’avait fait pour représenter les relatifs).

On a déjà écrit la méthode __add__() qui réalise l’addition. La méthode injecte(self,x) est là pour convertir x en une classe dans le même quotient que self.

Exercices

• Définissez les méthodes __neg__(self) et __sub__(self,x) pour l’opposé et la soustraction.
• Définissez une méthode canonique(self) qui retourne la représentation canonique de la classe (ZZ(a,n) avec 0 <= a < n).
• Modifiez toutes les méthodes pour assurer qu’on travaille toujours avec la représentation canonique (on gardera cette convention pour la suite).

Structure d’anneau

Comme pour l’addition, la multiplication dans $\mathbf{Z}$ induit une opération de monoïde commutatif sur $\mathbf{Z}/n\mathbf{Z}$ qui, avec l’addition, définit une structure d’anneau. Là encore c’est la construction standard d’anneau quotient par un idéal bilatère mais vous ne verrez (peut-être) cette notion générale qu’au prochain semestre.

Exercices

• Vérifiez que si $a_0 \equiv a_1 [n]$ et $b_0 \equiv b_1 [n]$ alors $a_0\times b_0 \equiv a_1\times b_1 [n]$. On peut donc poser $\bar a_n \times \bar b_n = \overline{a\times b}_n$.
• Vérifiez que l’opération précédente est associative, commutative, avec $\bar 1_n$ comme élément neutre, et qu’elle est distributive par rapport à l’addition.
• Définissez la méthode __mul__(self,x) pour la multiplication.
• Quels sont les éléments inversibles de $\mathbf{Z}/n\mathbf{Z}$?
• Définissez une méthode inverse(self) qui retourne l’inverse de self si c’est possible, et soulève l’exception ValueError sinon. (Souvenez vous de la démonstration de Bézout…)
• Déduisez-en une méthode __truediv__(self,x) qui retourne la valeur de self/x (lorsque $x$ est inversible) dans $\mathbf{Z}/n\mathbf{Z}$.

Théorème des restes chinois

Théorème. Si les $n_i$ pour $1\le i\le k$ sont deux-à-deux premiers entre eux alors pour tous $a_1,\dotsc,a_k\in\mathbf{Z}$, le système \[ \left\{ \begin{array}{rcl} x & \equiv & a_1 [n_1] \\ &\vdots& \\ x & \equiv & a_k [n_k] \end{array} \right. \] admet une unique solution modulo $n=\prod_{i=1}^{k} n_i$.

L’unicité modulo $n$ est facile: si on a deux solutions $x$ et $x'$, alors $x-x'$ est multiple de chacun des $n_i$, donc de leur PGCD $n$.

Pour l’existence, on pose $n'_i=\frac{n}{n_i}$ de sorte que $n_i\wedge n'_i=1$ pour $1\le i\le k$. Comme $\overline{(n'_i)}_{n_i}$ est inversible dans $\mathbf{Z}/{n_i}\mathbf{Z}$, on obtient $u_i$ tel que $u_in'_i=1 [n_i]$. On a aussi $u_in'_i=0 [n_j]$ pour tout $j\not=i$ puisque $n_j\mid n'_i$. On pose $x=\sum_{i=1}^{k} a_iu_in'_i$.

Exercice

• Écrivez une fonction restes_chinois(l) qui prend en argument une liste de couples l qui fournit le $k$-uplet $((a_1,n_1),\dotsc,(a_k,n_k))$, et qui retourne une solution au système ci-dessus (lorsque les $n_i$ sont deux-à-deux premiers entre eux).

Groupe des unités

L’ensemble des éléments multiplicativement inversibles forme un groupe (avec la multiplication comme loi): le groupe des unités $\mathbf{Z}/n\mathbf{Z}^{\times}$ (c’est une construction générale dans tout anneau). Dans le cas de $\mathbf{Z}/n\mathbf{Z}$, on a en plus la propriété que les unités sont exactement les générateurs additifs:

Exercice

• Montrez que $x\in\mathbf{Z}/n\mathbf{Z}^{\times}$ ssi pour tout $y\in\mathbf{Z}/n\mathbf{Z}$ il existe $k\in\mathbf{N}$ t.q. $y=kx=\bar k_n x$.

Indicatrice d’Euler

On note $φ(n)$ le cardinal de $\mathbf{Z}/n\mathbf{Z}^{\times}$: c’est la fonction indicatrice d’Euler. De manière équivalente, $φ(n)$ est le nombre d’entiers naturels $k< n$ premiers avec $n$.

Théorème d’Euler. Si $a$ est premier avec $n$ alors $a^{φ(n)}\equiv 1[n]$.

Une preuve élémentaire de ce théorème consiste à observer que, comme $\mathbf{Z}/n\mathbf{Z}^{\times}$ est un groupe, si $a$ est premier avec $n$ alors l’application $x\mapsto \bar a_n x$ est une bijection de $\mathbf{Z}/n\mathbf{Z}^{\times}$ dans lui-même, et donc $\prod_{x\in\mathbf{Z}/n\mathbf{Z}^{\times}} x =\prod_{x\in\mathbf{Z}/n\mathbf{Z}^{\times}} \bar a_n x$, ce qui donne $(\bar a_n)^{φ(n)}=\bar 1_n$ en simplifiant par le produit.

Exercices

• Proposez un algorithme naïf pour calculer l’indicatrice d’Euler. Que pensez-vous de sa complexité?
• Vérifiez que $φ(p^{k+1})=(p-1)p^k$ quand $p$ est premier.
• Pour tous $m,n\in\mathbf{N}^\bullet$, vérifiez que la fonction $\bar{k}_{mn}\in\mathbf{Z}/mn\mathbf{Z}\mapsto\bar{k}_{n}\in\mathbf{Z}/n\mathbf{Z}$ est correctement définie, et qu’elle se restreint en une fonction $\mathbf{Z}/mn\mathbf{Z}^{\times}\to\mathbf{Z}/n\mathbf{Z}^{\times}$.
• Montrez que la fonction $\bar{k}_{mn}\in\mathbf{Z}/mn\mathbf{Z}^{\times} \mapsto(\bar{k}_{m},\bar{k}_{n})\in\mathbf{Z}/m\mathbf{Z}^{\times}\times \mathbf{Z}/n\mathbf{Z}^{\times}$ est une bijection lorsque $m$ et $n$ sont premiers entre eux.
• Déduisez-en que si $m$ et $n$ sont premiers entre eux alors $φ(mn)=φ(m)φ(n)$.
• Déduisez de ce qui précède un autre algorithme pour calculer $φ(n)$ dans le cas général, via sa décomposition en facteur premiers. Que pensez-vous de sa complexité?