IP331.com | Online Tools

Algebra Tools Geometry Tools Trigonometry Tools Matrix Tools Function Tools Number Theory Tools Base Converter Electronics & Physics Statistics Tools Life & Finance

Home›Number Theory Tools›Primitive Root Checker

Primitive Root Checker

Check whether g is a primitive root modulo n

candidate g

mod n

Primitive Root Formula

g is primitive mod n if ord_n(g) = phi(n)

ord_n(g) is the least k with g^k ≡ 1 (mod n)

A primitive root is a generator of the multiplicative group modulo n. The practical test is to compute the order of the candidate and compare it with Euler phi of the modulus.

⚠ Not every modulus has primitive roots. This checker tests a candidate value rather than searching all possible generators.

What Is a Primitive Root?

A primitive root modulo n is a number whose powers generate every invertible residue modulo n. It is a key object in cyclic modular groups.

Generator

Its powers produce all units modulo n.

Order Test

The order must equal phi(n).

Coprime Required

A primitive root must be coprime to n.

Discrete Logs

Primitive roots support discrete logarithm problems.

Example: For g = 2 and n = 9, phi(9)=6 and ord_9(2)=6, so 2 is a primitive root modulo 9.

Applications of Primitive Roots

Cyclic Groups Discrete Logs Modular Arithmetic Cryptography Math Generators

Frequently Asked Questions

What is a primitive root checker?▼

It tests whether a number g generates all units modulo n, meaning its multiplicative order equals phi(n).

What formula defines a primitive root?▼

g is a primitive root modulo n if ord_n(g) = phi(n).

How do I use this primitive root calculator?▼

Enter candidate g and modulus n. The tool computes phi(n), finds the order of g, and compares them.

Does every modulus have a primitive root?▼

No. Primitive roots exist only for specific moduli such as 2, 4, odd prime powers, and twice odd prime powers.

Where are primitive roots used?▼

Primitive roots are used in cyclic groups, discrete logarithms, Diffie-Hellman style math, and modular arithmetic theory.

More Number Theory Tools

Smith Number Checker

Check if sum of digits equals sum of digits of prime factors (Smith number)

›

Euler Totient Calculator

Compute Euler's totient φ(n) — count of integers coprime to n

›

Prime Factorization Calculator

Decompose positive integers into prime factors with step-by-step trial division

›

Square-Free Number Checker

Check whether an integer is square-free using prime factorization

›

Lucky Number Sieve Calculator

Generate and test lucky numbers using the Josephus elimination sieve process

›

Twin Prime Checker

Check whether n and n+2 are both prime and form a twin prime pair

›