L’anneau \mathbb{Z}/n\mathbb{Z} est d’une importance capitale en arithmétique et en cryptographie. C’est en effet le cadre parfait de l’arithmétique modulaire. On le retrouve notamment au programme de deuxième année de prépa en MP et en MPI. Voici donc l’essentiel à savoir sur cet anneau. On pourra trouver, en lien avec cet anneau, des exercices corrigés d’arithmétique sur le petit théorème de Fermat en cliquant ici.
Table des matières
Pré-requis
- Bases sur les groupes finis (définition, ordre d’un élément, théorème de Lagrange)
- Bases sur les anneaux (définition, idéaux…)
Cours
Dans la suite, n sera un entier supérieur ou égal à 1.
Construction de l’anneau
Il y a plusieurs manières de construire \mathbb{Z}/n\mathbb{Z} . La première, celle que l’on voit en prépa, est de définir une relation d’équivalence sur \mathbb{Z} en disant que deux entiers a et b sont en relation si et seulement si ils ont le même reste dans la division euclidienne par n . Puis on vérifie à la main que l’on peut mettre une structure d’anneau sur l’ensemble des classes d’équivalences (qui sont 0, 1, …, n-1).
Si l’on connaît la théorie des anneaux quotients, on peut juste dire que c’est le quotient de \mathbb{Z} par l’idéal n\mathbb{Z} . D’ailleurs, ces deux constructions sont équivalentes.
On obtient donc dans tout les cas que ( \mathbb{Z}/n\mathbb{Z}, +, \times) est un anneau commutatif et que son cardinal est n .
Structure de groupe
Vu en tant que groupe, ( \mathbb{Z}/n\mathbb{Z}, +) est un groupe monogène (donc abélien), à savoir qu’il est généré par un seul élément : 1.
On peut s’intéresser au fait de savoir si ce groupe possède d’autres générateurs. On peut voir que d est un générateur du groupe \mathbb{Z}/n\mathbb{Z} si et seulement si d est premier avec n (c’est une conséquence du théorème de Bézout).
Les sous-groupes de (\mathbb{Z}/n\mathbb{Z}, +) sont connus eux aussi : il s’agit des multiples d’un élément d avec d un diviseur de n . L’ordre (additif) d’un tel élément étant \frac{n}{d} , le théorème de Lagrange nous dit que ce sous-groupe est de cardinal \frac{n}{d} . En fait on a mieux : si d divise n , alors (\mathbb{Z}/n\mathbb{Z}, +) possède un unique sous-groupe de cardinal \frac{n}{d} , qui est constitué des multiples de d .
Ce groupe est isomorphe à un autre groupe célèbre : le groupe des racines n- èmes de l’unité. Cet isomorphisme est donné explicitement par k \mapsto e^{\frac{2 i \pi k }{n}} .
Structure d’anneau
Vu en tant qu’anneau, ( \mathbb{Z}/n\mathbb{Z}, +, \times) est un anneau commutatif fini.
On peut se demander quand est-ce qu’il est intègre, c’est à dire que l’équation ab = 0 implique que a ou b soit nul. Cet anneau est intègre si et seulement si n est un nombre premier. S’il ne l’est pas, ses diviseurs de zéros (les éléments a non-nul tel qu’il existe b non-nul vérifiant ab = 0 ) sont exactement les diviseurs de n .
La question des inversibles de ( \mathbb{Z}/n\mathbb{Z}, +, \times) est aussi naturelle à se poser. Un élément a est inversible dans ( \mathbb{Z}/n\mathbb{Z}, +, \times) si et seulement si il est premier avec n . On note (\mathbb{Z}/n\mathbb{Z})^* l’ensemble des inversibles de \mathbb{Z}/n\mathbb{Z} . Ces éléments forment un groupe dont nous rappellerons les propriétés principales par la suite.
Ces deux remarques précédentes nous permettent de dire que ( \mathbb{Z}/n\mathbb{Z}, +, \times) est un corps si et seulement si n est premier. Si p est un nombre premier, on privilégiera la notation \mathbb{F}_p lorsque l’on parlera du corps à p éléments (on peut en effet montrer qu’il existe un unique corps à p éléments, à savoir \mathbb{Z}/p\mathbb{Z} ).
Structure du groupe multiplicatif
L’ensemble (\mathbb{Z}/n\mathbb{Z})^* munit de la loi \times est un groupe commutatif. Cela se vérifie facilement en revenant aux axiomes d’un groupe. Contrairement au groupe additif, il est compliqué d’obtenir des informations sur les éléments de ce groupe. On connaît cependant quelques propriétés générales sur ce dernier.
Du fait que a est inversible modulo n si et seulement si PGCD(a,n) = 1 , on en déduit que le cardinal de (\mathbb{Z}/n\mathbb{Z})^* est \varphi(n) avec \varphi l’indicatrice d’Euler.
On en déduit de là deux résultats fondamentaux. Le premier est le petit théorème de Fermat. En effet, si p est premier, alors \varphi(p) = p - 1 . On obtient alors du théorème de Lagrange que si a est non-nul modulo p , on a a^{p-1} = 1 [p] . Si l’on généralise ce fait à un entier qui n’est plus premier, on obtient toujours du théorème de Lagrange que si a est premier avec n , alors a^{\varphi(n)} = 1 [n] .
Théorème des restes chinois
On pourrait faire un article entier sur ce théorème tant il est important ! Il permet notamment de résoudre des systèmes de congruence. On va juste rappeler ici son énoncé.
Le théorème des restes chinois dit que si deux entiers n et m sont premiers entre-eux, alors les anneaux \mathbb{Z}/n\mathbb{Z} \times \mathbb{Z}/m\mathbb{Z} et \mathbb{Z}/nm\mathbb{Z} sont isomorphes. On obtient l’isomorphisme à l’aide du théorème de Bézout et de l’algorithme d’Euclide (on a explicitement besoin de ces derniers).
Pour aller plus loin
Ces résultats sur l’anneau \mathbb{Z}/n\mathbb{Z} permettent de faire beaucoup de choses. On citera ici quelques applications mathématiques directes qui permettent d’aller plus loin (qui sait, certains feront peut-être l’objet d’articles sur le site ? N’hésitez pas à nous le dire !) :
- On peut s’amuser à essayer de déterminer les idéaux et les éléments nilpotents de l’anneau \mathbb{Z}/n\mathbb{Z} .
- Le cryptosystème RSA se base entièrement sur le théorème des restes chinois et sur les propriétés générales de l’anneau \mathbb{Z}/n\mathbb{Z} .
- On a rapidement parlé de corps finis et vu que les \mathbb{Z}/p\mathbb{Z} en sont. Mais ce ne sont pas les seuls ! On peut en trouver de cardinal 4, 8, 9… Mais pas 10 ! Les corps finis ont un cardinal qui est une puissance d’un nombre premier. Ces derniers possèdent d’importantes propriétés qui sont extrêmement utiles en cryptographie plus avancée.
- En voyant le groupe additif \mathbb{Z}/n\mathbb{Z} comme le groupe des racines n-èmes de l’unité, on peut faire de la transformée de Fourier discrète, très utile en théorie du signal.
