What is a primitive root modulo n?

It's an integer g such that every number coprime to n can be written as some power of g modulo n — g 'generates' the entire multiplicative group modulo n.

Does every n have a primitive root?

No — primitive roots exist only for n = 1, 2, 4, pᵏ (an odd prime power), or 2pᵏ. For other values, like n = 8 or n = 15, no primitive root exists.

How do you test whether g is a primitive root?

Compute φ(n) and its distinct prime factors q₁, q₂, .... Then g is a primitive root if and only if gcd(g, n) = 1 and g^(φ(n)/qᵢ) mod n ≠ 1 for every prime factor qᵢ.

Why does this test work?

The order of g must divide φ(n) by Lagrange's theorem. If g's order were a proper divisor of φ(n), it would divide φ(n)/q for some prime factor q, making g^(φ(n)/q) ≡ 1. Ruling that out for every prime factor confirms the order is exactly φ(n).

Is the primitive root unique?

No — if g is a primitive root mod n, there are exactly φ(φ(n)) primitive roots in total. This calculator returns the smallest one.

How large a value of n can this calculator handle?

This calculator supports n up to 1,000,000, which keeps both factoring n and searching for the primitive root fast using trial division.

Where are primitive roots used in real life?

They're fundamental to Diffie-Hellman key exchange and the ElGamal cryptosystem, both of which rely on a public generator of a large prime-order multiplicative group.

How is this related to Euler's Totient Function Calculator?

Finding primitive roots requires computing φ(n) and factoring it — this calculator uses the same factorization approach as the site's Euler's Totient Function Calculator as a core step.

Primitive Root Calculator — Find the Smallest Primitive Root Modulo n

Our Primitive Root Calculator finds the smallest primitive root modulo n — an integer g whose powers g¹, g², g³, ... cycle through every unit modulo n before repeating. It first checks whether a primitive root exists at all (they only exist for n = 1, 2, 4, pᵏ, or 2pᵏ for an odd prime p), then searches using Euler's totient function and its prime factorization to test each candidate efficiently.

Quick Answer

A primitive root g mod n generates every unit modulo n via its powers. Enter n below to find the smallest one, with an automatic check for whether a primitive root exists at all.

Enter n, then click Calculate.

How to Use the Primitive Root Calculator — Find a Generator mod n

1
Enter a positive whole number n (up to 1,000,000).
2
Click 'Calculate' to find the smallest primitive root modulo n, if one exists.
3
Review φ(n) and the prime factors of φ(n) used in the verification.

Why Use Primitive Root Calculator — Find a Generator mod n?

A primitive root modulo n is a generator of the group of integers coprime to n under multiplication: its successive powers produce every unit modulo n exactly once before cycling back to 1, at exactly φ(n) steps. Not every n has one — primitive roots only exist for n = 1, 2, 4, an odd prime power pᵏ, or twice an odd prime power 2pᵏ, a classical result in number theory. This calculator checks that condition first, then efficiently verifies each candidate g by testing g^(φ(n)/q) mod n for every prime factor q of φ(n) — g is a primitive root exactly when none of those tests equal 1.

Frequently Asked Questions

Related Tools

Euler's Totient Function Calculator — φ(n) Online

Calculate Euler's totient function φ(n) — the count of integers from 1 to n coprime to n — via prime factorization. Free calculator showing the full factorization.

Modular Exponentiation Calculator — Fast bᵉ mod m Online

Calculate bᵉ mod m for arbitrarily large exponents using fast square-and-multiply exponentiation. Free calculator with BigInt precision, essential for cryptography.

Modular Multiplicative Inverse Calculator — Solve ax ≡ 1 (mod m)

Find the modular multiplicative inverse of a modulo m using the extended Euclidean algorithm. Free calculator with BigInt precision and existence check.

Group Theory Order Calculator — Element Order in ℤₙ Online

Find the order of an element in (ℤₙ, +) or (ℤ/nℤ)ˣ, with a Lagrange's theorem divisibility check shown as a step. Free calculator, instant results.