Toutes les racines primitives modulo n

Il détermine d’abord si le module appartient à une famille qui admet des racines primitives, puis calcule l’indicatrice d’Euler, trouve un générateur et en déduit tous les autres. La réponse contient le module, l’indicatrice, le nombre de racines et leur liste complète. Les valeurs inférieures à deux et les modules sans racine primitive produisent une erreur claire. La même arithmétique déterministe permet des vérifications rapides et une automatisation reproductible via API pour $0.002 par requête réussie.

Signification de la liste complète des racines primitives

Une racine primitive modulo n est un résidu dont les puissances successives engendrent chaque classe inversible modulo n. Le mot essentiel est « chaque » : un nombre peut être premier avec n tout en ne parcourant qu’un sous-groupe propre. Être une unité est donc nécessaire, mais insuffisant. Cette capacité renvoie tous les représentants positifs entre 1 et n moins 1 dont l’ordre multiplicatif vaut exactement phi(n). Pour le module 14, par exemple, le groupe des unités comprend six éléments et l’ensemble complet des générateurs contient deux résidus. La réponse indique n, l’indicatrice d’Euler phi, le nombre de racines primitives et le tableau primitive_roots trié numériquement. Le nombre sert de contrôle : lorsque des racines primitives existent, il vaut phi(phi(n)). Le module particulier 2 possède bien l’unique racine 1. Un module sans générateur de tout son groupe est explicitement refusé ; une liste vide masquerait le caractère non cyclique du groupe.

Vérification de l’existence et de chaque générateur

Les racines primitives n’existent pas pour tout module. Le théorème de classification affirme que le groupe multiplicatif modulo n est cyclique exactement lorsque n vaut 2, 4, une puissance d’un nombre premier impair ou le double d’une telle puissance. Le calculateur factorise n et contrôle cette condition avant toute recherche. Pour un module admissible, il calcule phi(n), factorise l’ordre du groupe et teste les unités candidates par exponentiation modulaire. Un candidat g est d’ordre phi(n) si, pour chaque diviseur premier distinct q de phi(n), g élevé à phi(n) divisé par q n’est pas congru à 1 modulo n. Dès qu’un tel g est connu, toutes les racines sont les puissances g élevé à k où k est premier avec phi(n). L’implémentation énumère ces exposants, calcule exactement leurs résidus et trie le résultat. Aucun hasard, table externe, accès réseau ou horaire courant n’intervient ; une entrée identique donne toujours le même contenu numérique.

Utilisation du résultat en mathématiques et en logiciel

Les listes complètes sont utiles lorsqu’un problème demande davantage que la plus petite racine primitive. Les élèves peuvent comparer les résidus obtenus à des tables de puissances manuelles et comprendre pourquoi le nombre de générateurs vaut phi(phi(n)). Les enseignants peuvent préparer des corrigés qui acceptent toutes les réponses valides. Les développeurs peuvent créer des données de test pour des routines d’ordre multiplicatif, vérifier un code d’énumération ou choisir un générateur selon une règle applicative distincte. Les échecs sont également instructifs : les modules 8 et 15 montrent que de nombreux nombres composés ont un groupe d’unités non cyclique malgré plusieurs résidus inversibles. L’entrée est limitée à 10,000, car la réponse exhaustive peut contenir de nombreuses racines ; cette borne rend prévisibles le rendu, la taille de l’API et le temps d’exécution. Saisissez n comme entier ou chaîne décimale simple. Une requête réussie coûte $0.002 ; les entrées incorrectes ou non prises en charge sont clairement signalées.