Aller au contenu
OneKitly

Sept a deux racines primitives, huit n'en a aucune

Publié le 27/10/2026 · 3 min de lecture · Calculateurs du quotidien

Lena Hoffmann

Lena Hoffmann — Rédactrice Sciences & Éducation chez OneKitly

Mathématiques · Physique

Vérifié à partir de 2 sources

Voir le profil →
En bref

Une racine primitive modulo n est un nombre dont les puissances parcourent toute valeur première avec n avant de revenir à un. Modulo 7, le nombre 3 y parvient : 3, 2, 6, 4, 5, 1 — les six résidus, dans un ordre brouillé, puis retour au départ. Cinq fait de même, et rien d'autre : il y en a donc deux. Modulo 11, il y a quatre générateurs ; modulo 8, aucun : les puissances d'aucun nombre n'atteignent tous les candidats, car la structure s'y scinde en deux moitiés indépendantes au lieu de former un seul cycle. Le compte, quand des générateurs existent, vaut φ(φ(n)) — pour 7, φ(6) = 2, et pour 11, φ(10) = 4.

Publicité

Modulo 7, les nombres 3 et 5 engendrent chacun toute valeur non nulle par multiplications répétées. Modulo 8, rien n'y parvient ; modulo 11, il y a quatre générateurs.

Les modules qui marchent forment une courte liste

Des générateurs n'existent que pour 1, 2, 4, une puissance quelconque d'un premier impair, et le double d'une telle puissance — rien d'autre. Cela exclut d'emblée 8, 12 et 15, et explique que 9 marche là où 8 échoue, malgré leur petite taille commune. La raison est que la structure multiplicative modulo tout le reste se décompose en morceaux indépendants, et qu'aucun élément unique ne peut engendrer un produit de cycles indépendants. C'est un cas rare où la classification est complète, brève et vérifiable contre le calculateur en une minute — bon exemple d'un théorème plus utile qu'une recherche.

À quoi sert un générateur

En posséder un transforme la multiplication en addition. Toute valeur non nulle s'écrit comme le générateur élevé à une certaine puissance : multiplier deux valeurs revient donc à additionner leurs exposants — le tour que jouent les logarithmes avec les nombres ordinaires, en contexte fini. C'est cette correspondance qu'exploitent les protocoles d'échange de clés : élever un générateur commun à un exposant secret est facile, retrouver l'exposant à partir du résultat paraît difficile, si bien que deux parties peuvent s'accorder sur une valeur qu'aucune n'a transmise. Toute la construction dépend du groupe formant un seul cycle, ce que garantit précisément une racine primitive.

Combien
Quels modules ont des générateurs
ModuleGénérateursCombien
73, 52
92, 52
112, 6, 7, 84
8, 12, 15aucun0
Calculateur de racine primitiveTrouve les racines primitives modulo n — les générateurs g dont les puissances g¹, g², … parcourent tous les nombres premiers avec n avant de se répéter (ordre égal à φ(n)). Les racines primitives n'existent que si n vaut 1, 2, 4, pᵏ ou 2pᵏ pour un premier impair p ; l'outil donne la plus petite, le nombre exact φ(φ(n)) et les liste. Elles sont au cœur de la cryptographie à logarithme discret et de l'échange de clés Diffie–Hellman.Essayer l'outil →
Publicité

Questions fréquentes

Existe-t-il une formule pour la plus petite racine ?
Aucune n'est connue, et la recherche se fait par essais. Les candidats sont testés dans l'ordre et chaque test est bon marché — il suffit de vérifier que le candidat élevé à l'indicatrice divisée par chaque facteur premier ne vaut pas un — mais rien ne permet de prédire quel candidat réussira. En pratique, la plus petite racine est presque toujours un très petit nombre, deux, trois ou cinq, et les heuristiques annoncent une croissance extrêmement lente avec le module ; cette attente est bien étayée et non démontrée, forme récurrente des résultats dans ce coin du domaine.
Pourquoi le nombre de générateurs dépend-il de φ(φ(n)) ?
Parce qu'une fois un générateur trouvé, tout autre est l'une de ses puissances, et une puissance engendre tout le cycle exactement quand son exposant est premier avec la longueur du cycle. Le cycle a pour longueur φ(n) : le nombre d'exposants utilisables vaut donc φ(φ(n)), par l'argument de comptage qui définit l'indicatrice au départ. Modulo 7, le cycle a longueur 6, les exposants premiers avec 6 sont 1 et 5, et les deux générateurs 3 et 5 sont le premier générateur élevé à ces puissances. La double application de la même fonction n'est pas fortuite — c'est la même question posée sur les exposants au lieu des valeurs.

Articles qui pourraient t'intéresser

Tous les guides →
ExplicationSept puissance 256 compte 217 chiffres et on n'en écrit aucun7²⁵⁶ mod 13 vaut 9, et 2¹⁰⁰⁰ mod 1 000 000 007 vaut 688 423 210. Les deux sortent de huit ou dix élévations au carré, sans qu'aucun nombre du calcul ne dépasse le carré du module.ExplicationUne fonction qui ne répond jamais que −1, 0 ou 1La fonction de Möbius renvoie 0 pour 12 et 49, −1 pour 30 et 105, et 1 pour 6. Trois réponses possibles encodent tout le schéma de factorisation d'un nombre.ExplicationUn premier est le nombre premier avec presque tout ce qui le précèdeφ(97) = 96, la plus grande valeur qu'un nombre sous cent puisse atteindre. φ(36) vaut 12 et φ(100) vaut 40 — plus un nombre a de facteurs premiers distincts, moins il garde de compagnons.ExplicationLa division modulaire n'existe que si les nombres ne partagent aucun facteur3 a un inverse modulo 7 — c'est 5, puisque 15 laisse un reste de 1. 4 n'en a aucun modulo 8, car ils partagent le facteur 4, et aucun multiple de 4 ne laisse jamais un reste de 1.ExplicationVingt-sept demande 111 étapes, vingt-six en demande dixDivise par deux si c'est pair, triple et ajoute un si c'est impair. Depuis 27, la suite grimpe jusqu'à 9 232 avant de retomber ; depuis 26, tout est fini en dix coups.ExplicationUn nombre malheureux tombe toujours dans la même boucle de huitÉlève les chiffres au carré et additionne. 19 atteint 1 en quatre étapes. 4 non, et rien de ce qui échoue non plus — tout échec atterrit dans 4, 16, 37, 58, 89, 145, 42, 20 et tourne sans fin.

Outils similaires

Sources

Tu as repéré une erreur dans cet article ?