Groupe multiplicatif d'entiers modulo n -Multiplicative group of integers modulo n

Dans une arithmétique modulaire , les nombres entiers premiers entre eux (relativement premiers) à n de l'ensemble de n nombres entiers non négatifs forment un groupe pour la multiplication modulo n , appelé groupe multiplicatif des entiers modulo n . De manière équivalente, les éléments de ce groupe peuvent être considérés comme les classes de congruence , également connues sous le nom de résidus modulo n , qui sont premiers à n . D'où un autre nom est le groupe des classes de résidus primitifs modulo n . Dans la théorie des anneaux , une branche de l'algèbre abstraite , il est décrit comme le groupe d'unités de l'anneau des entiers modulo n . Ici, les unités se réfèrent aux éléments avec un inverse multiplicatif , qui, dans cet anneau, sont exactement ceux parmi les premiers à n . ${\displaystyle \{0,1,\dots ,n-1\}}$

Structure algébrique → Théorie des groupes Théorie des groupes
Notions de base Sous-groupe Sous-groupe normal Groupe quotient Produit (semi-) direct Homomorphismes de groupe noyau image somme directe produit de couronne Facile fini infini continu multiplicatif additif cyclique abélien dièdre nilpotent soluble action Glossaire de la théorie des groupes Liste des sujets de théorie des groupes
Groupes finis Classification des groupes simples finis cyclique en alternance Type de mensonge sporadique Le théorème de Cauchy Le théorème de Lagrange Théorèmes de Sylow théorème de Hall groupe p Groupe abélien élémentaire Groupe Frobenius Multiplicateur de Schur Groupe symétrique S n Klein quatre groupe V Groupe dièdre D n Groupe de quaternions Q Groupe dicyclique Dic n
Groupes discrets Treillis Entiers ( )${\displaystyle \mathbb {Z} }$ Groupe gratuit Groupes modulaires PSL(2, )${\displaystyle \mathbb {Z} }$ SL(2, )${\displaystyle \mathbb {Z} }$ Groupe arithmétique Treillis Groupe hyperbolique
Groupes topologiques et de Lie Solénoïde Cercle GL linéaire général ( n ) Linéaire spécial SL( n ) O orthogonal ( n ) Euclidien E( n ) Spécial orthogonal SO( n ) Unitaire U( n ) Unité spéciale SU( n ) Sp symplectique ( n ) G 2 F 4 E 6 E 7 E 8 Lorentz Poincaré Conforme Difféomorphisme Boucle Groupe de Lie de dimension infinie O(∞) SU(∞) Sp(∞)
Groupes algébriques Groupe algébrique linéaire Groupe réducteur Variété abélienne Courbe elliptique
v t e

Ce groupe quotient , généralement noté , est fondamental en théorie des nombres . Il a trouvé des applications dans la cryptographie , la factorisation d'entiers et les tests de primalité . Il est un commutatif , fini groupe dont l' ordre est donné par la fonction indicatrice d'Euler : Pour le premier n du groupe est cyclique et en général la structure est facile à décrire, mais même pour le premier n pas de formule générale pour trouver des générateurs est connu. ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$${\displaystyle |(\mathbb {Z} /n\mathbb {Z} )^{\times }|=\varphi (n).}$

Axiomes de groupe

C'est un exercice simple de montrer que, sous multiplication, l'ensemble des classes de congruence modulo n qui sont premiers entre eux à n satisfont les axiomes pour un groupe abélien .

En effet, a est premier à n si et seulement si pgcd ( a , n ) = 1 . Les entiers dans la même classe de congruence a ≡ b (mod n ) satisfont pgcd( a , n ) = pgcd( b , n ) , donc l'un est premier à n si et seulement si l'autre l'est. Ainsi, la notion de classes de congruence modulo n qui sont premiers à n est bien définie.

Puisque pgcd( a , n ) = 1 et pgcd( b , n ) = 1 implique pgcd( ab , n ) = 1 , l'ensemble des classes premiers de n est fermé par multiplication.

Integer multiplication respecte les classes de congruence, qui est, un ≡ a ' et b ≡ b' (mod n ) implique ab de la A'B » (mod n ) . Ceci implique que la multiplication est associative, commutative, et que la classe de 1 est l'unique identité multiplicative.

Enfin, étant donné a , l' inverse multiplicatif de a modulo n est un entier x satisfaisant ax 1 (mod n ) . Il existe précisément lorsque a est premier à n , car dans ce cas pgcd( a , n ) = 1 et par le lemme de Bézout il existe des entiers x et y satisfaisant ax + ny = 1 . Notez que l'équation ax + ny = 1 implique que x est premier à n , donc l'inverse multiplicatif appartient au groupe.

Notation

L'ensemble des (classes de congruence des) entiers modulo n avec les opérations d'addition et de multiplication est un anneau . Il est noté   ou    (la notation fait référence à la prise du quotient d'entiers modulo l' idéal ou constitué des multiples de n ). En dehors de la théorie des nombres, la notation la plus simple est souvent utilisée, bien qu'elle puisse être confondue avec les entiers p -adiques lorsque n est un nombre premier. ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$${\displaystyle \mathbb {Z} /(n)}$ ${\displaystyle n\mathbb {Z} }$${\style d'affichage (n)}$${\displaystyle \mathbb {Z} _{n}}$

Le groupe multiplicatif d'entiers modulo n , qui est le groupe d'unités de cet anneau, peut s'écrire (selon l'auteur)   (pour l'allemand Einheit , qui se traduit par unité ), , ou des notations similaires. Cet article utilise${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times },}$   ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{*},}$   ${\displaystyle \mathrm {U} (\mathbb {Z} /n\mathbb {Z} ),}$   ${\displaystyle \mathrm {E} (\mathbb {Z} /n\mathbb {Z} )}$${\displaystyle \mathbb {Z} _{n}^{*}}$${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }.}$

La notation se réfère au groupe cyclique d'ordre n . Il est isomorphe au groupe des entiers modulo n sous addition. Notez que ou peut également faire référence au groupe en cours d'ajout. Par exemple, le groupe multiplicatif pour un nombre premier p est cyclique et donc isomorphe au groupe additif , mais l'isomorphisme n'est pas évident. ${\displaystyle \mathrm {C} _{n}}$${\displaystyle \mathbb {Z} /n\mathbb {Z} }$${\displaystyle \mathbb {Z} _{n}}$${\displaystyle (\mathbb {Z} /p\mathbb {Z} )^{\times }}$${\displaystyle \mathbb {Z} /(p-1)\mathbb {Z} }$

Structure

L'ordre du groupe multiplicatif d'entiers modulo n est le nombre d'entiers parmi premiers à n . Elle est donnée par la fonction totient d'Euler : (séquence A000010 dans l' OEIS ). Pour p premier , . ${\displaystyle \{0,1,\dots ,n-1\}}$${\displaystyle |(\mathbb {Z} /n\mathbb {Z} )^{\times }|=\varphi (n)}$${\displaystyle \varphi (p)=p-1}$

Cas cyclique

Le groupe est cyclique si et seulement si n vaut 1, 2, 4, p ^k ou 2 p ^k , où p est un nombre premier impair et k > 0 . Pour toutes les autres valeurs de n, le groupe n'est pas cyclique. Cela a été prouvé pour la première fois par Gauss . ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$

Cela signifie que pour ces n :

${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }\cong \mathrm {C} _{\varphi (n)},}$ où ${\displaystyle \varphi (p^{k})=\varphi (2p^{k})=p^{k}-p^{k-1}.}$

Par définition, le groupe est cyclique si et seulement s'il possède une génératrice g (un groupe générateur { g } de taille un), c'est-à-dire que les puissances donnent tous les résidus possibles modulo n premiers à n (les premières puissances donnent à chacune exactement une fois ). Un générateur de est appelé racine primitive modulo n . S'il y a un générateur, alors il y en a. ${\displaystyle g^{0},g^{1},g^{2},\dots ,}$${\style d'affichage \varphi (n)}$${\displaystyle g^{0},\dots ,g^{\varphi (n)-1}}$${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$${\style d'affichage \varphi (\varphi (n))}$

Puissances de 2

Modulo 1 deux entiers quelconques sont congrus, c'est-à-dire qu'il n'y a qu'une seule classe de congruence, [0], premier à 1. Par conséquent, est le groupe trivial avec φ(1) = 1 élément. En raison de sa nature triviale, le cas des congruences modulo 1 est généralement ignoré et certains auteurs choisissent de ne pas inclure le cas de n = 1 dans les énoncés de théorème. ${\displaystyle (\mathbb {Z} /1\,\mathbb {Z} )^{\times }\cong \mathrm {C} _{1}}$

Modulo 2, il n'y a qu'une seule classe de congruence entre premiers, [1], de même que le groupe trivial . ${\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{\times }\cong \mathrm {C} _{1}}$

Modulo 4 il existe deux classes de congruence entre premiers, [1] et [3], donc le groupe cyclique à deux éléments. ${\displaystyle (\mathbb {Z} /4\mathbb {Z} )^{\times }\cong \mathrm {C} _{2},}$

Modulo 8, il existe quatre classes de congruence entre premiers, [1], [3], [5] et [7]. Le carré de chacun d'eux est 1, donc le groupe des quatre de Klein . ${\displaystyle (\mathbb {Z} /8\mathbb {Z} )^{\times }\cong \mathrm {C} _{2}\times \mathrm {C} _{2},}$

Modulo 16, il existe huit classes de congruences entre premiers [1], [3], [5], [7], [9], [11], [13] and [15]. est le sous-groupe 2- torsion (c'est-à-dire que le carré de chaque élément est 1), n'est donc pas cyclique. Les puissances de 3, sont un sous-groupe d'ordre 4, de même que les puissances de 5,   Ainsi${\displaystyle \{\pm 1,\pm 7\}\cong \mathrm {C} _{2}\times \mathrm {C} _{2},}$${\displaystyle (\mathbb {Z} /16\mathbb {Z} )^{\times }}$${\style d'affichage \{1,3,9,11\}}$${\style d'affichage \{1,5,9,13\}.}$${\displaystyle (\mathbb {Z} /16\mathbb {Z} )^{\times }\cong \mathrm {C} _{2}\times \mathrm {C} _{4}.}$

Le schéma illustré par 8 et 16 est valable pour les puissances supérieures 2 ^k , k > 2 : est le sous-groupe à 2 torsion (donc n'est pas cyclique) et les puissances de 3 sont un sous-groupe cyclique d'ordre 2 ^{k − 2} , donc${\displaystyle \{\pm 1,2^{k-1}\pm 1\}\cong \mathrm {C} _{2}\times \mathrm {C} _{2},}$${\displaystyle (\mathbb {Z} /2^{k}\mathbb {Z} )^{\times }}$${\displaystyle (\mathbb {Z} /2^{k}\mathbb {Z} )^{\times }\cong \mathrm {C} _{2}\times \mathrm {C} _{2^{k -2}}.}$

Nombres composés généraux

Par le théorème fondamental des groupes abéliens finis , le groupe est isomorphe à un produit direct de groupes cycliques d'ordres de puissance premiers. ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$

Plus précisément, le théorème des restes chinois dit que si alors l'anneau est le produit direct des anneaux correspondant à chacun de ses facteurs de puissance premiers : ${\displaystyle \;\;n=p_{1}^{k_{1}}p_{2}^{k_{2}}p_{3}^{k_{3}}\dots ,\;}$${\displaystyle \mathbb {Z} /n\mathbb {Z} }$

${\displaystyle \mathbb {Z} /n\mathbb {Z} \cong \mathbb {Z} /{p_{1}^{k_{1}}}\mathbb {Z} \;\times \;\mathbb { Z} /{p_{2}^{k_{2}}}\mathbb {Z} \;\times \;\mathbb {Z} /{p_{3}^{k_{3}}}\mathbb {Z } \points \;\;}$

De même, le groupe d'unités est le produit direct des groupes correspondant à chacun des facteurs de puissance premiers : ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$

${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }\cong (\mathbb {Z} /{p_{1}^{k_{1}}}\mathbb {Z} ) ^{\times }\times (\mathbb {Z} /{p_{2}^{k_{2}}}\mathbb {Z} )^{\times }\times (\mathbb {Z} /{p_{ 3}^{k_{3}}}\mathbb {Z} )^{\times }\dots \;.}$

Pour chaque puissance première impaire, le facteur correspondant est le groupe cyclique d'ordre , qui peut en outre se décomposer en groupes cycliques d'ordres de puissance première. Pour les puissances de 2, le facteur n'est pas cyclique à moins que k = 0, 1, 2, mais se divise en groupes cycliques comme décrit ci-dessus. ${\style d'affichage p^{k}}$${\displaystyle (\mathbb {Z} /{p^{k}}\mathbb {Z} )^{\times }}$${\displaystyle \varphi (p^{k})=p^{k}-p^{k-1}}$${\displaystyle (\mathbb {Z} /{2^{k}}\mathbb {Z} )^{\times }}$

L'ordre du groupe est le produit des ordres des groupes cycliques dans le produit direct. L' exposant du groupe, c'est-à-dire le plus petit commun multiple des ordres dans les groupes cycliques, est donné par la fonction de Carmichael (séquence A002322 dans l' OEIS ). En d'autres termes, est le plus petit nombre tel que pour chacun un premier avec n , est vrai . Il se divise et lui est égal si et seulement si le groupe est cyclique. ${\style d'affichage \varphi (n)}$ ${\style d'affichage \lambda (n)}$${\style d'affichage \lambda (n)}$${\displaystyle a^{\lambda (n)}\equiv 1{\pmod {n}}}$${\style d'affichage \varphi (n)}$

Sous-groupe de faux témoins

Si n est composé, il existe un sous-groupe du groupe multiplicatif, appelé "groupe des faux témoins", dans lequel les éléments, lorsqu'ils sont élevés à la puissance n − 1 , sont congrus à 1 modulo n . (Parce que le résidu 1 lorsqu'il est élevé à une puissance quelconque est congru à 1 modulo n , l'ensemble de ces éléments est non vide.) On pourrait dire, à cause du petit théorème de Fermat , que de tels résidus sont des « faux positifs » ou des « faux témoins » pour la primalité de n . Le nombre 2 est le résidu le plus souvent utilisé dans ce contrôle de primalité de base, donc 341 = 11 × 31 est célèbre puisque 2 ³⁴⁰ est congru à 1 modulo 341, et 341 est le plus petit nombre composé (par rapport à 2). Pour 341, le sous-groupe des faux témoins contient 100 résidus et est donc d'indice 3 à l'intérieur du groupe multiplicatif de 300 éléments mod 341.

Exemples

n = 9

Le plus petit exemple avec un sous-groupe non négligeable de faux témoins est 9 = 3 × 3 . Il y a 6 résidus premiers à 9 : 1, 2, 4, 5, 7, 8. Puisque 8 est congru à −1 modulo 9 , il s'ensuit que 8 ⁸ est congru à 1 modulo 9. Donc 1 et 8 sont des faux positifs pour la "primalité" de 9 (puisque 9 n'est pas réellement premier). Ce sont en fait les seuls, donc le sous-groupe {1,8} est le sous-groupe des faux témoins. Le même argument montre que n − 1 est un « faux témoin » pour tout composé n impair .

n = 91

Pour n = 91 (= 7 × 13), il existe des résidus premiers à 91, dont la moitié (soit 36 ​​d'entre eux) sont de faux témoins de 91, soit 1, 3, 4, 9, 10, 12, 16, 17 , 22, 23, 25, 27, 29, 30, 36, 38, 40, 43, 48, 51, 53, 55, 61, 62, 64, 66, 68, 69, 74, 75, 79, 81, 82 , 87, 88 et 90, puisque pour ces valeurs de x , x ⁹⁰ est congru à 1 mod 91. ${\style d'affichage \varphi (91)=72}$

n = 561

n = 561 (= 3 × 11 × 17) est un nombre de Carmichael , donc s ⁵⁶⁰ est congru à 1 modulo 561 pour tout entier s premier à 561. Le sous-groupe des faux témoins n'est, dans ce cas, pas propre ; c'est l'ensemble des unités multiplicatives modulo 561, qui est constitué de 320 résidus.

Exemples

Ce tableau montre la décomposition cyclique de et un générateur pour n 128. La décomposition et les générateurs ne sont pas uniques ; par exemple, ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$

${\displaystyle \displaystyle {\begin{aligned}(\mathbb {Z} /35\mathbb {Z} )^{\times }&\cong (\mathbb {Z} /5\mathbb {Z} )^{\ fois }\times (\mathbb {Z} /7\mathbb {Z} )^{\times }\cong \mathrm {C} _{4}\times \mathrm {C} _{6}\cong \mathrm { C} _{4}\times \mathrm {C} _{2}\times \mathrm {C} _{3}\cong \mathrm {C} _{2}\times \mathrm {C} _{12} \cong (\mathbb {Z} /4\mathbb {Z} )^{\times }\times (\mathbb {Z} /13\mathbb {Z} )^{\times }\\&\cong (\mathbb {Z} /52\mathbb {Z} )^{\times }\end{aligned}}}$

(mais ). Le tableau ci-dessous répertorie la décomposition la plus courte (parmi celles-ci, la première lexicographiquement est choisie - cela garantit que les groupes isomorphes sont répertoriés avec les mêmes décompositions). Le groupe électrogène est également choisi pour être le plus court possible, et pour n avec racine primitive, la plus petite racine primitive modulo n est répertoriée. ${\displaystyle \not \cong \mathrm {C} _{24}\cong \mathrm {C} _{8}\times \mathrm {C} _{3}}$

Par exemple, prenez . Alors signifie que l'ordre du groupe est 8 (c'est-à-dire qu'il y a 8 nombres inférieurs à 20 et premiers entre eux); signifie que l'ordre de chaque élément divise 4, c'est-à-dire que la quatrième puissance de tout nombre premier à 20 est congrue à 1 (mod 20). L'ensemble {3,19} génère le groupe, ce qui signifie que chaque élément de est de la forme 3 ^a × 19 ^b (où a vaut 0, 1, 2 ou 3, car l'élément 3 est d'ordre 4, et de même b est 0 ou 1, car l'élément 19 est d'ordre 2). ${\displaystyle (\mathbb {Z} /20\mathbb {Z} )^{\times }}$${\style d'affichage \varphi (20)=8}$${\style d'affichage \lambda (20)=4}$${\displaystyle (\mathbb {Z} /20\mathbb {Z} )^{\times }}$

Le plus petit mod racine primitif n est (0 si aucune racine n'existe)

0, 1, 2, 3, 2, 5, 3, 0, 2, 3, 2, 0, 2, 3, 0, 0, 3, 5, 2, 0, 0, 7, 5, 0, 2, 7, 2, 0, 2, 0, 3, 0, 0, 3, 0, 0, 2, 3, 0, 0, 6, 0, 3, 0, 0, 5, 5, 0, 3, 3, 0, 0, 2, 5, 0, 0, 0, 3, 2, 0, 2, 3, 0, 0, 0, 0, 2, 0, 0, 0, 7, 0, 5, 5, 0, 0, 0, 0, 3, 0, 2, 7, 2, 0, 0, 3, 0, 0, 3, 0, ... (séquence A046145 dans l' OEIS )

Les nombres des éléments dans un ensemble générateur minimal de mod n sont

0, 0, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 2, 1, 1, 1, 1, 2, 2, 1, 1, 3, 1, 1, 1, 2, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 3, 1, 2, 1, 2, 2, 1, 1, 3, 1, 1, 2, 2, 1, 1, 2, 3, 2, 1, 1, 3, 1, 1, 2, 2, 2, 2, 1, 2, 2, 2, 1, 3, 1, 1, 2, 2, 2, 2, 1, 3, 1, 1, 1, 3, 2, 1, 2, 3, 1, 2, ... (séquence A046072 dans l' OEIS )

Voir également

• Factorisation de la courbe elliptique de Lenstra

Remarques

Les références

Les Disquisitiones Arithmeticae ont été traduites du latin cicéronien de Gauss en anglais et en allemand . L'édition allemande comprend tous ses articles sur la théorie des nombres : toutes les preuves de réciprocité quadratique , la détermination du signe de la somme de Gauss , les enquêtes sur la réciprocité biquadratique , et des notes inédites.

• Gauss, Carl Friedrich ; Clarke, Arthur A. (traducteur en anglais) (1986), Disquisitiones Arithmeticae (deuxième édition corrigée) , New York: Springer , ISBN 978-0-387-96254-2
• Gauss, Carl Friedrich ; Maser, H. (traducteur en allemand) (1965), Untersuchungen uber hohere Arithmetik (Disquisitiones Arithemeticae & other papers on number theory) (Deuxième édition) , New York : Chelsea, ISBN 978-0-8284-0191-3
• Riesel, Hans (1994), Nombres premiers et méthodes informatiques pour la factorisation (deuxième édition) , Boston : Birkhäuser, ISBN 978-0-8176-3743-9
• Vinogradov, IM (2003), "§ VI RACINES ET INDICES PRIMITIFS" , Éléments de la théorie des nombres , Mineola, NY: Dover Publications, pp. 105-121, ISBN 978-0-486-49530-9

Liens externes

• Weisstein, Eric W. "Groupe de Multiplication Modulo" . MathWorld .
• Weisstein, Eric W. "Racine primitive" . MathWorld .
• Outil Web pour calculer de manière interactive des tables de groupe par John Jones