Racine primitive modulo n

Racine primitive modulo n

Les racines primitives modulo n sont un concept issu de l'arithmétique modulaire, dans la théorie des nombres.

Si n est un entier strictement positif, les nombres premiers avec n, pris modulo n, forment un groupe pour la multiplication ; écrit sous la forme (Z/nZ)× ou Zn*. Ce groupe est cyclique si et seulement si n est égal à 1 ou 2 ou 4 ou pk ou 2 pk pour un nombre premier impair p et k 1. Un générateur de ce groupe cyclique est appelé une racine primitive modulo n, ou un élément primitif de Zn*. Une racine primitive modulo n est donc un entier g tel que, modulo n, chaque autre entier est juste une puissance de g. La démonstration est donnée dans le paragraphe Groupe des unités de l'article Anneau Z/nZ.

Cette définition s'applique aussi aux nombres complexes de module un. Une racine primitive d'ordre n, si n est un entier positif est une racine nième tel que ses puissances engendrent toutes les racines d'ordre 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 nous avons 329, 3313, 3411, 355 et 361 (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 (suite A046145 de lOEIS:

n  racine primitive mod n
2 1
3 2
4 3
5 2
6 5
7 3
8 -
9 2
10 3
11 2
12 -
13 2
14 3

Voici une table donnant les plus petites racines primitives des nombres premiers inférieurs à mille (suite A001918 de lOEIS:

p r p r p r p r p r p r p r p r p r p r p r p r
2 1 47 5 109 6 191 7 269 2 353 3 439 15 523 2 617 3 709 2 811 3 907 2
3 2 53 2 113 3 193 5 271 6 359 7 443 2 541 2 619 2 719 11 821 2 911 7
5 2 59 2 127 3 197 2 277 5 367 6 449 3 547 2 631 3 727 5 823 3 919 7
7 3 61 2 131 2 199 3 281 3 373 2 457 13 557 2 641 3 733 6 827 2 929 3
11 2 67 2 137 3 211 2 283 3 379 2 461 2 563 2 643 11 739 3 829 2 937 5
13 2 71 7 139 2 223 3 293 2 383 5 463 3 569 3 647 5 743 5 839 11 941 2
17 3 73 5 149 2 227 2 307 5 389 2 467 2 571 2 653 2 751 3 853 2 947 2
19 2 79 3 151 6 229 6 311 11 397 5 479 13 577 5 659 2 757 2 857 3 953 3
23 5 83 2 157 5 233 3 313 10 401 3 487 3 587 2 661 2 761 3 859 2 967 5
29 2 89 3 163 2 239 7 317 2 409 21 491 2 593 3 673 5 769 11 863 5 971 2
31 3 97 5 167 5 241 7 331 2 419 2 499 7 599 7 677 2 773 2 877 2 977 3
37 2 101 2 173 2 251 2 337 10 421 2 503 5 601 7 683 2 787 2 881 3 983 5
41 6 103 5 179 2 257 3 347 2 431 7 509 2 607 3 691 3 797 2 883 2 991 6
43 3 107 2 181 2 263 5 349 2 433 5 521 3 613 2 701 2 809 3 887 5 997 7

Aucune formule générale simple pour calculer les racines primitives modulo n n'est connue. Il existe néanmoins des méthodes pour localiser une racine primitive qui est plus rapide qu'un simple essai de tous les candidats. Si l'ordre multiplicatif d'un nombre m modulo n est égal à φ(n) (l'ordre de Zn*), alors il est une racine primitive. Nous pouvons utiliser ceci pour tester les racines primitives :

premièrement calculons φ(n). Puis, déterminons les différents facteurs premiers de φ(n), soit p1,...,pk. Maintenant, pour chaque élément m de (Z/nZ)×, calculons
m^{\phi(n)/p_i}\mod n \qquad\mbox{  for } i=1,\ldots,k

en utilisant par exemple la méthode d'exponentiation rapide. Dès que nous trouvons un nombre m pour lequel ces k résultants sont tous différents de 1, nous stoppons : m est une racine primitive.

Le nombre de racines primitives modulo n est égal à φ(φ(n)) comme, en général, un groupe cyclique de r éléments possède φ(r) générateurs.

Pour tout nombre premier p, notons gp la plus petite racine primitive modulo p (entre 1 et p-1). Nous avons les résultats suivants. Pour chaque ε>0 il existe une constante C telle que pour tout p, gp < C p1/4+ε. Si l'hypothèse généralisée de Riemann est vraie, alors gp = O(ln6 p).

Voir aussi

Conjecture d'Artin sur les racines primitives


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Racine primitive modulo n de Wikipédia en français (auteurs)

Игры ⚽ Нужен реферат?

Regardez d'autres dictionnaires:

  • Racine Primitive Modulo N — Les racines primitives modulo n sont un concept issu de l arithmétique modulaire, dans la théorie des nombres. Si n≥1 est un entier, les nombres premiers avec n, pris modulo n, forment un groupe muni de la multiplication ; écrit sous la… …   Wikipédia en Français

  • NOMBRES (THÉORIE DES) - Nombres algébriques — Les mathématiciens grecs avaient découvert que certains rapports de grandeurs ne sont pas rationnels, c’est à dire qu’ils ne sont pas égaux au rapport de deux entiers: il en est ainsi du rapport de la diagonale d’un carré à son côté, puisque… …   Encyclopédie Universelle

  • DIVISIBILITÉ — L’étude élémentaire de la divisibilité dans l’anneau Z des entiers relatifs résulte de l’existence de la division euclidienne qui entraîne que cet anneau est principal. Les propriétés générales des anneaux principaux sont exposées dans l’article… …   Encyclopédie Universelle

  • Decimale recurrente — Développement décimal périodique Premières décimales de quelques rationnels En mathématiques, le développement décimal périodique d un nombre rationnel est une écriture qui explicite la suite des décimales de …   Wikipédia en Français

  • Décimale Récurrente — Développement décimal périodique Premières décimales de quelques rationnels En mathématiques, le développement décimal périodique d un nombre rationnel est une écriture qui explicite la suite des décimales de …   Wikipédia en Français

  • Décimale récurrente — Développement décimal périodique Premières décimales de quelques rationnels En mathématiques, le développement décimal périodique d un nombre rationnel est une écriture qui explicite la suite des décimales de …   Wikipédia en Français

  • Développement décimal périodique — Premières décimales de quelques rationnels En mathématiques, le développement décimal périodique d un nombre rationnel est une écriture qui explicite la suite des décimales de ce nombre, en indiquant un bloc de chiffres qui se répète à l infini.… …   Wikipédia en Français

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

  • Liste des articles de mathematiques — Projet:Mathématiques/Liste des articles de mathématiques Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou probabilités et statistiques via l un des trois bandeaux suivants  …   Wikipédia en Français

  • Ordre multiplicatif — En mathématiques et plus précisément en arithmétique modulaire, soit un entier relatif a et un entier naturel n avec pgcd(a,n) = 1, l ordre multiplicatif de a modulo n est le plus petit entier k > 0 tel que ak ≡ 1 (modulo n). L ordre de a… …   Wikipédia en Français

Share the article and excerpts

Direct link
https://fr-academic.com/dic.nsf/frwiki/1402926 Do a right-click on the link above
and select “Copy Link”