Primitive Root Calculator

Explore multiplicative cycles modulo an integer with MiniWebtool’s Primitive Root Calculator. It finds primitive roots when they exist, reports Euler’s totient, and uses power tables and cyclic-group diagrams to explain the generated residues.

Need help using this tool? Ask AI

Gemini (copy & open)

For Gemini, paste the copied question into the chat. You can also copy it below.

View the question

Help me understand MiniWebtool's Primitive Root Calculator: https://miniwebtool.com/primitive-root-calculator/. What can I use it for, what inputs or settings do I need, and how do I use it and understand the output? Walk me through one simple example. Use this page as your source and answer in English.

3 free uses dailyNo sign-up requiredInstant Results

Primitive Root CalculatorTry it now — free ▼

Primitive root: its powers hit every residue (3 yes, 2 no, mod 7)

Enter a modulus below to get all its primitive roots, Euler's totient and the power tables.

Embed Primitive Root Calculator Widget

About Primitive Root Calculator

The Primitive Root Calculator finds all primitive roots of a given modulus n — integers g whose powers \(g^1, g^2, \ldots, g^{\varphi(n)}\) generate every element of the multiplicative group \((\mathbb{Z}/n\mathbb{Z})^*\). Enter any positive integer to instantly see all primitive roots, Euler's totient \(\varphi(n)\), an interactive cyclic group visualization, a power table, and a step-by-step verification of the smallest primitive root.

At a Glance

Primitive Root Calculator lists every primitive root of a positive integer modulus n and reports Euler's totient. It also shows a power table, a cyclic group wheel for small moduli and a worked check of the smallest root.

Primitive Root Calculator: features at a glance
Feature	What you get	Good for
Modulus input	Enter any positive integer n, or use the example buttons for n = 7, 13, 9, 14, 12 and 97.	Exploring how existence depends on n
All primitive roots	Lists every primitive root, their count and the group order. If none exist, as for n = 12, it says so.	Number theory exercises and cryptography examples
Euler's totient	Reports phi(n); the number of primitive roots, when they exist, is phi(phi(n)).	Checking the count of roots by formula
Cyclic group wheel	For n up to 100, an interactive wheel animates how a chosen root generates every unit through its powers.	Seeing how a generator cycles through the group
Power table	A grid shows g^k mod n for k = 1 to phi(n), with primitive roots and the identity highlighted.	Verifying a root by inspection
Verification steps	Walks through a step-by-step check of the smallest primitive root.	Learning the test using prime factors of phi(n)

Applications of Primitive Roots

🔐

Diffie-Hellman

Key exchange protocol uses primitive roots as generators

🔏

ElGamal Encryption

Public-key cryptosystem based on discrete logarithms

✍

Digital Signatures

DSA and Schnorr signatures rely on generators of large prime-order subgroups

🎲

Pseudorandom Numbers

Linear congruential generators use primitive root properties

📡

Error-Correcting Codes

Reed-Solomon and BCH codes use generators of finite fields

🧮

Number Theory

Index calculus, quadratic residues, and discrete logarithm problems

Key Concepts and Formulas

Primitive Root Calculator: Key Concepts and Formulas
Concept	Formula / Definition	Description
Primitive Root	\(\text{ord}_n(g) = \varphi(n)\)	An integer g whose order mod n equals Euler's totient
Euler's Totient	\(\varphi(n) = n \prod_{p\|n}\left(1 - \frac{1}{p}\right)\)	Count of integers in [1, n] coprime to n
Existence Criterion	\(n \in \{1, 2, 4, p^k, 2p^k\}\)	Primitive roots exist only for these forms (p odd prime)
Number of Roots	\(\varphi(\varphi(n))\)	Count of primitive roots when they exist
Primitive Root Test	\(g^{\varphi(n)/p} \not\equiv 1 \pmod{n}\) for all primes \(p \| \varphi(n)\)	Sufficient condition: check only for prime factors of φ(n)
Generating All Roots	\(g^k \bmod n\) where \(\gcd(k, \varphi(n)) = 1\)	Once one root g is found, all others follow

Understanding Primitive Roots

A primitive root modulo n is an integer g such that \(\{g^1 \bmod n, g^2 \bmod n, \ldots, g^{\varphi(n)} \bmod n\}\) equals the set of all integers from 1 to n−1 that are coprime to n. In group-theoretic terms, g is a generator of the cyclic multiplicative group \((\mathbb{Z}/n\mathbb{Z})^*\). For example, 3 is a primitive root mod 7 because the powers 3¹=3, 3²=2, 3³=6, 3⁴=4, 3⁵=5, 3⁶=1 (mod 7) produce every element of {1, 2, 3, 4, 5, 6}.

When Do Primitive Roots Exist?

A classic result in number theory (proved by Gauss) states that primitive roots modulo n exist if and only if n is one of: 1, 2, 4, p^k, or 2p^k, where p is an odd prime and k ≥ 1. For other values of n, the group \((\mathbb{Z}/n\mathbb{Z})^*\) is not cyclic — it decomposes as a direct product of cyclic groups by the Chinese Remainder Theorem — so no single element can generate the entire group. For instance, \((\mathbb{Z}/8\mathbb{Z})^* \cong \mathbb{Z}/2 \times \mathbb{Z}/2\) has no primitive root.

How to Find Primitive Roots Efficiently

The standard algorithm works in two phases. Phase 1: find the smallest primitive root by trial. For each candidate g starting from 2, compute \(g^{\varphi(n)/p} \bmod n\) for every prime factor p of \(\varphi(n)\). If none of these equals 1, then g is a primitive root. In practice, the smallest primitive root is typically small — it is conjectured to be \(O(n^\epsilon)\) for any \(\epsilon > 0\). Phase 2: once a primitive root g is known, all other primitive roots are \(g^k \bmod n\) where \(\gcd(k, \varphi(n)) = 1\), giving exactly \(\varphi(\varphi(n))\) primitive roots in total.

How to Use the Primitive Root Calculator

Enter the modulus n: Type a positive integer in the input field, or click one of the quick example buttons to auto-fill a value.
Click Find Primitive Roots: Press the button to compute all primitive roots modulo n.
Review the results: See the count, the complete list of primitive roots, Euler's totient, group order, and whether primitive roots exist for your n.
Explore the visualization: For n ≤ 100, the interactive cyclic group wheel shows how each primitive root generates the entire group through its powers. Click on any root chip to see its cycle animated on the wheel.
Study the power table: The grid shows g^k mod n for k = 1, 2, …, φ(n), with primitive roots and the identity element highlighted in distinct colors.

Primitive Roots in Cryptography

Primitive roots play a central role in modern cryptography. In the Diffie-Hellman key exchange, two parties agree on a large prime p and a primitive root g mod p, then exchange public keys g^a mod p and g^b mod p. The shared secret g^ab mod p is computationally infeasible for an eavesdropper to determine, because computing discrete logarithms in large cyclic groups is believed to be hard. Similarly, ElGamal encryption and the Digital Signature Algorithm (DSA) both rely on the difficulty of the discrete logarithm problem in groups generated by primitive roots.

FAQ

What is a primitive root modulo n?

A primitive root modulo n is an integer g such that the powers g¹, g², …, g^φ(n) modulo n produce every integer coprime to n exactly once. Equivalently, g has multiplicative order equal to φ(n), meaning g generates the entire multiplicative group (Z/nZ)*.

For which values of n do primitive roots exist?

Primitive roots exist if and only if n is 1, 2, 4, p^k, or 2p^k, where p is an odd prime and k is a positive integer. For example, n = 7 (prime), n = 9 (3²), and n = 14 (2 × 7) all have primitive roots, but n = 8, n = 12, and n = 15 do not.

How many primitive roots does n have?

If n has primitive roots, then the number of primitive roots modulo n equals φ(φ(n)), where φ is Euler's totient function. For example, n = 7 has φ(φ(7)) = φ(6) = 2 primitive roots, which are 3 and 5.

How do you find primitive roots?

To find primitive roots of n: first compute φ(n) and factorize it. Then for each candidate g coprime to n, check if g^(φ(n)/p) is not congruent to 1 mod n for every prime factor p of φ(n). If all checks pass, g is a primitive root. All other roots can be found as g^k mod n where gcd(k, φ(n)) = 1.

Why are primitive roots important in cryptography?

Diffie-Hellman key exchange, ElGamal encryption, and digital signature algorithms such as DSA and Schnorr use generators of large prime-order subgroups, whose order q divides p−1. Their security relies on the difficulty of the discrete logarithm problem in these subgroups.

Reference this content, page, or tool as:

"Primitive Root Calculator" at https://MiniWebtool.com/primitive-root-calculator/ from MiniWebtool, https://MiniWebtool.com/

by miniwebtool team. Updated: 2026-04-16

Developer API available: Run this tool from your app, automation, or agent with one JSON HTTP request. View API docs

Chat with your favorite AI

Gemini (copy & open)

For Gemini, paste the copied question into the chat. You can also copy it below.

View the question

Help me understand MiniWebtool's Primitive Root Calculator: https://miniwebtool.com/primitive-root-calculator/. What can I use it for, what inputs or settings do I need, and how do I use it and understand the output? Walk me through one simple example. Use this page as your source and answer in English.

Primitive Root Calculator

About Primitive Root Calculator

At a Glance

Applications of Primitive Roots

Key Concepts and Formulas

Understanding Primitive Roots

When Do Primitive Roots Exist?

How to Find Primitive Roots Efficiently

How to Use the Primitive Root Calculator

Primitive Roots in Cryptography

FAQ

Chat with your favorite AI

Advanced Math Operations:

Math Solver

Numbers & factors

Fractions & division

Powers, roots & logs

Algebra & equations

Calculus

Geometry & trigonometry

Top & Updated:

Download everything as one ZIP with Pro