Racine primitive modulo n | EPFL Graph Search

Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?

Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.

Découvrez-en plus sur les applications Graph.

Les racines primitives modulo n sont un concept issu de l'arithmétique modulaire, dans la théorie des nombres. Ce sont (lorsqu'il en existe) les générateurs du groupe des inversibles de l'anneau Z/nZ. Si n est un entier strictement positif, les nombres premiers avec n, pris modulo n, forment un groupe pour la multiplication, noté (Z/nZ) ou Z. Ce groupe est cyclique si et seulement si n est égal à 4 ou p ou 2p pour un nombre premier p ≥ 3 et k ≥ 0. Un générateur de ce groupe cyclique est appelé une racine primitive modulo n, ou un élément primitif de Z. Une racine primitive modulo n est donc un entier g tel que tout inversible dans Z/nZ est une puissance de g modulo n. Prenons par exemple n = 14. Les éléments de (Z/14Z) sont les classes de congruence 1, 3, 5, 9, 11 et 13. Donc 3 est une racine primitive modulo 14, et l'on a 3 ≡ 9, 3 ≡ 13, 3 ≡ 11, 3 ≡ 5 et 3 ≡ 1 (modulo 14). La seule autre racine primitive modulo 14 est 5. Voici une table contenant les plus petites racines primitives pour quelques valeurs de n () : Voici une table donnant les plus petites racines primitives r modulo les nombres premiers p inférieurs à () : On ne connait aucune formule générale simple pour calculer les racines primitives modulo n. Il existe cependant une méthode pour tester si un entier m est racine primitive mod n — c'est-à-dire si son ordre multiplicatif modulo n est égal à φ(n) (l'ordre de Z) — qui est plus rapide qu'un simple calcul mod n de toutes ses puissances successives jusqu'à l'exposant φ(n) : Les racines primitives mod n sont les racines dans Z/nZ du φ(n)-ième polynôme cyclotomique Φ. Pour tout nombre premier p, le n-ième polynôme cyclotomique Φ est irréductible sur le corps fini Z si et seulement si p est une racine primitive modulo n. Par conséquent, les entiers n modulo lesquels il n'existe pas de racine primitive () sont ceux tels que Φ est réductible sur tous les Z. Ce sont également les entiers modulo lesquels 1 a d'autres racines carrées que 1 et –1.

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (1)

Concepts associés (19)

Cours associés (3)

Séances de cours associées (43)

COM-102: Advanced information, computation, communication II

Text, sound, and images are examples of information sources stored in our computers and/or communicated over the Internet. How do we measure, compress, and protect the informatin they contain?

COM-401: Cryptography and security

This course introduces the basics of cryptography. We review several types of cryptographic primitives, when it is safe to use them and how to select the appropriate security parameters. We detail how

CS-101: Advanced information, computation, communication I

Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics a

Nombre de Fermat

thumb|Le mathématicien français Pierre de Fermat (1601-1665) étudia les propriétés des nombres portant maintenant son nom. Un nombre de Fermat est un nombre qui peut s'écrire sous la forme 22n + 1, avec n entier naturel. Le n-ième nombre de Fermat, 22n + 1, est noté Fn. Ces nombres doivent leur nom à Pierre de Fermat, qui émit la conjecture que tous ces nombres étaient premiers. Cette conjecture se révéla fausse, F5 étant composé, de même que tous les suivants jusqu'à F32.

Racine primitive modulo n

Multiplicative group of integers modulo n

In modular arithmetic, the integers coprime (relatively prime) to n from the set of n non-negative integers form a group under multiplication modulo n, called the multiplicative group of integers modulo n. Equivalently, the elements of this group can be thought of as the congruence classes, also known as residues modulo n, that are coprime to n. Hence another name is the group of primitive residue classes modulo n. In the theory of rings, a branch of abstract algebra, it is described as the group of units of the ring of integers modulo n.

Let u(q)(g) be the small quantum group associated with a complex semisimple Lie algebra g and a primitive root of unity q, satisfying certain restrictions. We establish the equivalence between three different actions of g on the center of u(q)(g) and on the higher derived center of u(q)(g). Based on the triviality of this action for g = sl(2), sl(3), sl(4), we conjecture that, in finite type A, central elements of the small quantum group u(q)(Sl(n)) arise as the restriction of central elements in the big quantum group u(q)(sl(n)). We also study the role of an ideal z(Hig) known as the Higman ideal in the center of u(q)(g). We show that it coincides with the intersection of the Harish-Chandra center and its Fourier transform, and compute the dimension of z(Hig) in type A. As an illustration we provide a detailed explicit description of the derived center of u(q)(sl(2)) and its various symmetries.

SPRINGER INTERNATIONAL PUBLISHING AG2021

Sans titre

Sans titre COM-102: Advanced information, computation, communication II

Classement des groupes finites abeliens MATH-310: Algebra

Couvre le théorème de classification pour les groupes abéliens finis et introduit les anneaux, y compris les diviseurs zéro et les domaines.