Ordre multiplicatif et racines primitives
Multiplions sans cesse par un même nombre a, modulo n : on finit toujours par revenir à 1. Le nombre de pas est l'ordre de a. Quand un seul a suffit à parcourir tous les restes, c'est une racine primitive, et les restes deviennent les heures d'une seule horloge. Cette idée explique la période du développement décimal de 1/7, permet de calculer avec des logarithmes modulo p, règle les générateurs de nombres pseudo-aléatoires et dit combien de mélanges parfaits remettent un jeu de cartes en ordre.
Vue d'ensemble
La page sur Fermat et Euler a montré que aφ(n) ≡ 1 (mod n) quand a est premier avec n. L'ordre de a est le plus petit exposant k ≥ 1 tel que ak ≡ 1 ; il divise toujours φ(n). Voici ce qu'on en tire :
| Idée | Énoncé | Application |
|---|---|---|
| ordre de a modulo n | divise φ(n), et même λ(n) | tests de primalité, période des suites |
| racine primitive | existe exactement pour n = 1, 2, 4, pk, 2pk (Gauss) | indices, Diffie-Hellman |
| ordre de 10 modulo p | longueur de la période de 1/p | 1/7 = 0,142857 142857… |
| ordre de 2 modulo 2n − 1 | nombre de mélanges parfaits pour revenir au départ | 8 pour un jeu de 52 cartes |
L'ordre d'un élément : la longueur du cycle des puissances
Chaque ligne du tableau est une suite de puissances qui tourne en rond.
Dans le tableau, la ligne de a contient a, a², a³… modulo n. Elle revient à 1 au bout de ord(a) pas, puis se répète. Comme les puissances de a forment un sous-groupe des φ(n) restes inversibles, le théorème de Lagrange impose que ord(a) divise φ(n). Quand n est premier, il y a exactement φ(d) éléments d'ordre d pour chaque diviseur d de n − 1, et en particulier φ(n − 1) racines primitives.
Les racines primitives : quand tout tient dans un seul cycle
Une racine primitive engendre tous les restes inversibles par ses seules puissances.
Gauss a démontré en 1801 qu'il existe une racine primitive modulo n exactement quand n vaut 1, 2, 4, pk ou 2pk, avec p premier impair. Modulo 8, par exemple, tout élément inversible vérifie a² ≡ 1 : aucun n'est d'ordre 4. Il y a alors φ(φ(n)) racines primitives. Pour tester g, inutile de calculer toutes ses puissances : il suffit de vérifier gφ(n)/q ≢ 1 pour chaque facteur premier q de φ(n). La plus petite racine primitive modulo p est presque toujours petite, mais pas bornée. Artin a conjecturé en 1927 que 2 est racine primitive pour environ 37,4 % des premiers ; c'est démontré sous l'hypothèse de Riemann généralisée (Hooley, 1967).
Les indices : des logarithmes modulo p
Avec une racine primitive, multiplier revient à additionner des exposants.
Si g est une racine primitive modulo p, tout reste non nul a s'écrit a ≡ gi pour un unique i entre 0 et p − 2 : c'est l'indice de a, un logarithme discret. On a ind(ab) ≡ ind(a) + ind(b) (mod p − 1), exactement comme ln(ab) = ln a + ln b. Les tables d'indices, publiées par Jacobi en 1839 (Canon arithmeticus, pour tous les premiers jusqu'à 1 000), servaient de règle à calcul modulaire. Elles résolvent aussi les équations xk ≡ a (mod p) : il suffit de résoudre k·ind(x) ≡ ind(a) (mod p − 1), une congruence du premier degré.
La période du développement de 1/p
Dans la division posée de 1 par p, les restes successifs sont les puissances de 10 modulo p.
Quand on divise 1 par 7, les restes sont 1, 3, 2, 6, 4, 5, puis de nouveau 1 : ce sont 10k mod 7. La période de 1/p a donc pour longueur l'ordre de 10 modulo p, un diviseur de p − 1. Quand 10 est racine primitive, la période est maximale (p − 1 chiffres) : 7, 17, 19, 23, 29, 47, 59, 61, 97… Le bloc obtenu est un nombre cyclique : 142 857 × 2 = 285 714, × 3 = 428 571… en sont des permutations circulaires. Et si la période est paire, ses deux moitiés ont pour somme 999…9 (théorème de Midy, 1836) : 142 + 857 = 999.
Signature : la structure du groupe, le hasard simulé, les mélanges parfaits
Trois usages de l'ordre, de l'algèbre aux cartes à jouer.
Quand il n'y a pas de racine primitive, le plus grand ordre possible est λ(n), introduit par Carmichael en 1910 : c'est le plus petit exposant tel que aλ(n) ≡ 1 pour tous les a premiers avec n. Il divise φ(n) et se calcule par les restes chinois : λ est le PPCM des λ(pk), avec λ(pk) = φ(pk) pour p impair et λ(2k) = 2k−2 pour k ≥ 3. Le groupe des inversibles se décompose alors en produit de groupes cycliques. Un nombre composé n est de Carmichael exactement quand λ(n) divise n − 1 : c'est pourquoi il trompe le test de Fermat.
Les ordinateurs fabriquent du hasard par une récurrence xk+1 = a·xk mod m (Lehmer, 1949). La suite revient à son départ après ord(a) pas : pour une période maximale, a doit être une racine primitive modulo m. Le « générateur minimal standard » de Park et Miller (1988) prend m = 2³¹ − 1, premier, et a = 16 807 = 7⁵, racine primitive : la période vaut 2 147 483 646. Mais la suite n'est pas vraiment aléatoire : les couples (xk, xk+1) tombent sur un petit nombre de droites parallèles (Marsaglia, 1968). Le générateur RANDU d'IBM (a = 65 539, m = 2³¹) était si mauvais que tous ses triplets tombent sur 15 plans.
Un mélange « américain » parfait coupe le jeu en deux moitiés égales et intercale exactement les cartes une à une. Dans le mélange « extérieur », la carte du dessus reste dessus ; pour 2n cartes, la carte en position i (comptée à partir de 0) va en position 2i mod (2n − 1). Le nombre de mélanges qui remettent le jeu dans l'ordre est donc l'ordre de 2 modulo 2n − 1 : 8 pour un jeu de 52 cartes, alors qu'il faut 52 mélanges intérieurs (ordre de 2 modulo 53). Les magiciens connaissent bien ce phénomène (Diaconis, Graham et Kantor, 1983).
Une brève histoire
En résumé
L'ordre
Les puissances d'un élément inversible tournent en rond ; la longueur du cycle divise φ(n), et même λ(n).
La racine primitive
Elle existe pour 1, 2, 4, pk, 2pk ; elle fait de la multiplication une addition d'indices, et de chaque reste une heure d'une même horloge.
Partout des cycles
Période de 1/p, période d'un générateur pseudo-aléatoire, mélanges de cartes : chaque fois, c'est l'ordre d'un nombre qui compte.
Pour aller plus loin
La conjecture d'Artin est démontrée en un sens faible : Heath-Brown a prouvé en 1986 que l'un au moins des nombres 2, 3, 5 est racine primitive pour une infinité de premiers, sans pouvoir dire lequel.
Les registres à décalage (LFSR) utilisent la même idée dans le corps fini à 2k éléments : un polynôme primitif donne une période maximale 2k − 1, utilisée dans les GPS et les télécommunications.
Liens. Fermat, Euler et restes chinois ; résidus quadratiques ; tests de primalité et cryptographie (Diffie-Hellman) ; corps finis.