Qu'est-ce qu'une racine primitive modulo n ?

C'est un entier g tel que tout nombre premier avec n peut s'écrire comme une puissance de g modulo n — g 'génère' tout le groupe multiplicatif modulo n.

Tous les n ont-ils une racine primitive ?

Non — les racines primitives n'existent que pour n = 1, 2, 4, pᵏ (une puissance première impaire), ou 2pᵏ. Pour d'autres valeurs, comme n = 8 ou n = 15, aucune racine primitive n'existe.

Comment teste-t-on si g est une racine primitive ?

Calculez φ(n) et ses facteurs premiers distincts q₁, q₂, .... Alors g est une racine primitive si et seulement si pgcd(g, n) = 1 et g^(φ(n)/qᵢ) mod n ≠ 1 pour chaque facteur premier qᵢ.

Pourquoi ce test fonctionne-t-il ?

L'ordre de g doit diviser φ(n) selon le théorème de Lagrange. Si l'ordre de g était un diviseur propre de φ(n), il diviserait φ(n)/q pour un certain facteur premier q, rendant g^(φ(n)/q) ≡ 1. Écarter cela pour chaque facteur premier confirme que l'ordre est exactement φ(n).

La racine primitive est-elle unique ?

Non — si g est une racine primitive mod n, il y a exactement φ(φ(n)) racines primitives au total. Cette calculatrice renvoie la plus petite.

Quelle valeur de n cette calculatrice peut-elle gérer ?

Cette calculatrice prend en charge des valeurs de n jusqu'à 1 000 000, ce qui garde à la fois la factorisation de n et la recherche de la racine primitive rapides grâce à la division d'essai.

Où les racines primitives sont-elles utilisées dans la vie réelle ?

Elles sont fondamentales pour l'échange de clés Diffie-Hellman et le cryptosystème ElGamal, tous deux reposant sur un générateur public d'un grand groupe multiplicatif d'ordre premier.

Comment cela se rapporte-t-il à la Calculatrice de la Fonction Indicatrice d'Euler ?

Trouver des racines primitives nécessite de calculer φ(n) et de le factoriser — cette calculatrice utilise la même approche de factorisation que la Calculatrice de la Fonction Indicatrice d'Euler du site comme étape centrale.

Calculatrice de Racine Primitive — Trouver la Plus Petite Racine Primitive Modulo n

Notre Calculatrice de Racine Primitive trouve la plus petite racine primitive modulo n — un entier g dont les puissances g¹, g², g³, ... parcourent chaque unité modulo n avant de se répéter. Elle vérifie d'abord si une racine primitive existe (elles n'existent que pour n = 1, 2, 4, pᵏ, ou 2pᵏ pour un nombre premier impair p), puis effectue une recherche en utilisant la fonction indicatrice d'Euler et sa factorisation première pour tester efficacement chaque candidat.

Réponse rapide

Une racine primitive g mod n génère chaque unité modulo n par ses puissances. Saisissez n ci-dessous pour trouver la plus petite, avec une vérification automatique de l'existence d'une racine primitive.

Saisissez n, puis cliquez sur Calculer.

Comment utiliser Calculatrice de Racine Primitive — Trouver un Générateur mod n

1
Saisissez un entier positif n (jusqu'à 1 000 000).
2
Cliquez sur 'Calculer' pour trouver la plus petite racine primitive modulo n, si elle existe.
3
Consultez φ(n) et les facteurs premiers de φ(n) utilisés dans la vérification.

Pourquoi utiliser Calculatrice de Racine Primitive — Trouver un Générateur mod n ?

Une racine primitive modulo n est un générateur du groupe des entiers premiers avec n sous la multiplication : ses puissances successives produisent chaque unité modulo n exactement une fois avant de revenir à 1, en exactement φ(n) étapes. Tous les n n'en ont pas — les racines primitives n'existent que pour n = 1, 2, 4, une puissance première impaire pᵏ, ou le double d'une puissance première impaire 2pᵏ, un résultat classique en théorie des nombres. Cette calculatrice vérifie d'abord cette condition, puis vérifie efficacement chaque candidat g en testant g^(φ(n)/q) mod n pour chaque facteur premier q de φ(n) — g est une racine primitive exactement lorsqu'aucun de ces tests n'est égal à 1.

Questions fréquentes

Outils similaires

Calculatrice de la Fonction Indicatrice d'Euler — φ(n) en Ligne

Calculez la fonction indicatrice d'Euler φ(n) — le nombre d'entiers de 1 à n premiers avec n — via la factorisation en nombres premiers. Calculatrice gratuite affichant la factorisation complète.

Calculatrice d'Exponentiation Modulaire — bᵉ mod m Rapide en Ligne

Calculez bᵉ mod m pour des exposants arbitrairement grands en utilisant l'exponentiation rapide par élévation au carré et multiplication. Calculatrice gratuite avec précision BigInt, essentielle pour la cryptographie.

Calculatrice d'Inverse Multiplicatif Modulaire — Résoudre ax ≡ 1 (mod m)

Trouvez l'inverse multiplicatif modulaire de a modulo m en utilisant l'algorithme d'Euclide étendu. Calculatrice gratuite avec précision BigInt et vérification d'existence.

Calculateur d'Ordre en Théorie des Groupes — Ordre d'Élément dans ℤₙ en Ligne

Trouvez l'ordre d'un élément dans (ℤₙ, +) ou (ℤ/nℤ)ˣ, avec une vérification de divisibilité du théorème de Lagrange montrée comme étape. Calculateur gratuit, résultats instantanés.