IP331.com | Online Tools

Algebra Geometry Trigonometry Matrices Functions Number Theory Base Converter Electronics Statistics Life & Finance Simulators

Home›Number Theory›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

Aliquot Sequence Calculator

Compute the sum-of-proper-divisors sequence and detect perfect/amicable/sociable numbers

›

Legendre Symbol Calculator

Evaluate the Legendre symbol and check quadratic residue status modulo an odd prime

›

Modular Square Root Calculator

Compute x satisfying x^2 = a (mod p) using Euler criterion and Tonelli-Shanks

›

Harshad Number Calculator

Test if a number is divisible by the sum of its digits (Niven number)

›

Perfect & Amicable Number Checker

Determine if a number is perfect, amicable, or ordinary

›

Perfect Power Checker

Test whether an integer can be written as a^k with k greater than 1

›