Primitive Root Calculator

Use this Primitive Root Calculator to enter values, adjust options, and review results in a compact responsive workspace.

Results are calculated automatically as you enter data.

Modulus n Candidate g (optional) List roots when n <=

Show generated powers

Order test and phi factorization

Result Enter a modulus.

Disclaimer: All tools on this site are intended for educational and informational purposes only. Exact integer output for accepted inputs; not professional advice. Verify definitions, assumptions, and method before relying on results. See our Terms of Use.

Assumptions and limitations

This Primitive Root Calculator is for educational and informational use. Accepted inputs produce exact integer outputs based on the definitions and methods shown on the page. They are not professional advice, and important results should be independently verified before being used for decisions. For professional, safety-sensitive, construction, engineering, official, or high-cost uses, verify results with an appropriate method, current standards, required tolerances, and a qualified professional. Use of this calculator is subject to our Terms of Use.

▼ See explanations and tips below ▼

Related Calculators

What Is a Primitive Root?

A primitive root is a number whose powers generate all the invertible residues for a chosen modulus. In modular arithmetic, the modulus $n$ sets the cycle of remainders. Only numbers that are coprime to $n$ are invertible modulo $n$, and those invertible residues are called the units modulo $n$.

A number $g$ is a primitive root modulo $n$ when the powers of $g$ produce every unit modulo $n$ before the sequence returns to $1$. In group language, $g$ is a generator of the multiplicative group of units modulo $n$.

For example, modulo $7$, the units are $1,2,3,4,5,6$. The powers of $3$ give

$$ 3^0,3^1,3^2,3^3,3^4,3^5,3^6 \pmod{7} = 1,3,2,6,4,5,1. $$

The sequence reaches every nonzero residue modulo $7$ before returning to $1$, so $3$ is a primitive root modulo $7$.

Primitive roots do not exist for every modulus. For $n \ge 2$, primitive roots exist exactly when

$$ n = 2, \quad n = 4, \quad n = p^k, \quad \text{or} \quad n = 2p^k, $$

where $p$ is an odd prime and $k \ge 1$.

For a blank candidate, the calculator finds a generator modulo $p$, checks whether it lifts directly to $p^2$, adjusts it by $p$ when required, and chooses the odd representative for $2p^k$. The constructed value is then independently verified to have order $\varphi(n)$.

Why Primitive Roots Matter

Primitive roots connect several core ideas in number theory: modular arithmetic, greatest common divisors, Euler's totient function, cyclic groups, and modular exponentiation. They help answer a practical question: can one starting value generate every invertible residue modulo $n$ by repeated multiplication?

This matters in several settings:

Students use primitive roots to understand how modular multiplication behaves.
Number theory learners use them to study cyclic groups and reduced residue systems.
Competitive programmers use related tests when working with modular arithmetic, generators, and prime moduli.
Cryptography learners meet similar generator ideas when studying discrete logarithms and key-exchange examples.

Primitive roots are useful for learning and experimentation, but choosing parameters for real cryptographic systems requires specialized standards and expert review.

Key Terms to Know

Modulus: The number $n$ used to define remainders in modular arithmetic.
Residue: A remainder class modulo $n$. For example, $20 \equiv 2 \pmod{18}$.
Coprime: Two integers are coprime when their greatest common divisor is $1$.
Unit modulo $n$: A residue that is coprime to $n$ and therefore has a multiplicative inverse modulo $n$.
Reduced residue system: The complete set of residues modulo $n$ that are coprime to $n$.
Euler's totient function: $\varphi(n)$, the number of units modulo $n$.
Multiplicative order: The smallest positive exponent $d$ such that $g^d \equiv 1 \pmod{n}$, assuming $g$ is a unit modulo $n$.
Generator: An element whose powers produce every element of a group. A primitive root is a generator of the unit group modulo $n$.

How Primitive Roots Work

Primitive roots are built from three linked ideas: which residues are units, how many units there are, and how long a power cycle lasts.

First, a candidate $g$ must be a unit modulo $n$. That means

$$ \gcd(g,n)=1. $$

If $g$ is not coprime to $n$, it cannot be a primitive root because its powers cannot move through the full set of invertible residues.

Second, the size of the unit set is $\varphi(n)$. If

$$ n = p_1^{e_1}p_2^{e_2}\cdots p_r^{e_r}, $$

then Euler's totient function can be computed as

$$ \varphi(n)=n\prod_{i=1}^{r}\left(1-\frac{1}{p_i}\right). $$

Equivalently,

$$ \varphi(n)=\prod_{i=1}^{r}p_i^{e_i-1}(p_i-1). $$

Third, the multiplicative order of $g$ modulo $n$ is the length of the power cycle before returning to $1$:

$$ \operatorname{ord}_n(g)=\min\{d\ge 1: g^d\equiv 1\pmod{n}\}. $$

A unit $g$ is a primitive root exactly when

$$ \operatorname{ord}_n(g)=\varphi(n). $$

That means the cycle is as long as possible: it visits every unit exactly once before repeating.

The Prime-Divisor Test

A direct way to test a candidate is to factor $\varphi(n)$ and check the prime divisors of $\varphi(n)$. If $g$ is a unit modulo $n$, then $g$ is primitive when

$$ g^{\varphi(n)/q}\not\equiv 1\pmod{n} $$

for every prime divisor $q$ of $\varphi(n)$.

This works because the order of any unit divides $\varphi(n)$. If the order is a proper divisor of $\varphi(n)$, then at least one of these reduced-exponent checks will return $1$, showing that the candidate's cycle is too short.

Examples of Primitive Roots in Practice

Example 1: A Prime Modulus

Let $n=7$ and test $g=3$.

Since $7$ is prime,

$$ \varphi(7)=6. $$

The powers of $3$ modulo $7$ are

$$ \begin{aligned} 3^0 &\equiv 1 \pmod{7},\\ 3^1 &\equiv 3 \pmod{7},\\ 3^2 &\equiv 2 \pmod{7},\\ 3^3 &\equiv 6 \pmod{7},\\ 3^4 &\equiv 4 \pmod{7},\\ 3^5 &\equiv 5 \pmod{7},\\ 3^6 &\equiv 1 \pmod{7}. \end{aligned} $$

The residues $1,3,2,6,4,5$ are all six units modulo $7$. Therefore,

$$ \operatorname{ord}_7(3)=6=\varphi(7), $$

so $3$ is a primitive root modulo $7$.

Example 2: A Composite Modulus With Primitive Roots

Let $n=18$ and test $g=5$.

The prime factorization is

$$ 18=2\cdot 3^2, $$

$$ \varphi(18)=18\left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right)=6. $$

The units modulo $18$ are

$$ 1,5,7,11,13,17. $$

The powers of $5$ modulo $18$ are

$$ 5^0,5^1,5^2,5^3,5^4,5^5,5^6 \pmod{18} =1,5,7,17,13,11,1. $$

The cycle reaches all six units before returning to $1$, so

$$ \operatorname{ord}_{18}(5)=6=\varphi(18). $$

Thus $5$ is a primitive root modulo $18$.

Example 3: A Modulus With No Primitive Roots

Let $n=8$. The units modulo $8$ are

$$ 1,3,5,7, $$

so $\varphi(8)=4$. Try $g=3$:

$$ 3^1\equiv 3\pmod{8}, \qquad 3^2=9\equiv 1\pmod{8}. $$

The order of $3$ modulo $8$ is $2$, not $4$. Similar short cycles occur for the other units. Also, $8$ is not one of the forms $2$, $4$, $p^k$, or $2p^k$ with $p$ an odd prime, so primitive roots do not exist modulo $8$.

How to Interpret the Result

A primitive-root result has two separate parts: the status of the modulus and the status of the candidate.

Primitive roots exist tells you whether the modulus $n$ is one of the allowed forms. This depends only on $n$, not on the candidate $g$.

$\varphi(n)$ tells you how many units exist modulo $n$. If a primitive root exists, a primitive root's power cycle has length $\varphi(n)$.

Candidate order tells you the length of the candidate's cycle. If the order equals $\varphi(n)$, the candidate is a primitive root. If the order is smaller, the candidate generates only part of the unit set.

Not a unit means the candidate is not coprime to the modulus. In that case, the candidate does not have a multiplicative order in the unit group and cannot be a primitive root.

Listed roots: skipped means the modulus is larger than the selected listing limit. It does not mean primitive roots fail to exist.

The power sequence starts with $k=0$, where $g^0\equiv 1\pmod{n}$, and stops at its first return to $1$. When the candidate is primitive, it visits every unit once. Displays longer than 241 terms show only $k=0$ through $k=240$ and are explicitly labeled as truncated.

Common Mistakes and Misconceptions

A common mistake is assuming every modulus has primitive roots. Many moduli, such as $8$, $12$, $15$, and $16$, do not.

Another mistake is testing a candidate that is not coprime to the modulus. For example, $g=6$ cannot be a primitive root modulo $18$ because $\gcd(6,18)=6$.

Some users confuse $n$ with $\varphi(n)$. The modulus controls the remainders, but $\varphi(n)$ controls the maximum possible order of a unit.

It is also easy to read a skipped root list as a negative result. A skipped list only means the calculator did not list all roots because of the selected limit.

Rounding is not part of the mathematics here. Primitive roots, orders, factorizations, and residues are exact integer results. Decimal or fractional inputs do not belong in this calculation.

Finally, a displayed power sequence may not show the full cycle. The exact order remains reported, while long tables and plots stop at $k=240$ and state that the return at $k=\operatorname{ord}_n(g)$ is not displayed.

When to Use Primitive Roots

Use primitive roots when you want to:

Check whether a modulus has a generator for its unit residues.
Test whether a specific candidate $g$ generates all units modulo $n$.
Study multiplicative order and cyclic behavior in modular arithmetic.
Compare prime moduli, prime powers, and composite moduli.
Build intuition for discrete logarithm examples and modular exponentiation.
Inspect reduced residue systems through a power sequence.

Primitive roots are especially helpful when learning why multiplication modulo $n$ can behave very differently depending on the factorization of $n$.

Limitations and Things to Keep in Mind

This calculation uses exact integer modular arithmetic. The modulus must be an integer from $2$ to $1,000,000,000$. A candidate may be any integer from $-1,000,000,000$ to $1,000,000,000$; it is normalized to its canonical residue from $0$ through $n-1$.

The selected list limit from $20$ to $500$ controls only whether every primitive root is enumerated. If $n$ is larger than this limit, the calculator still determines existence, constructs one root when possible, calculates the exact order, and reports the theoretical root count $\varphi(\varphi(n))$.

When no candidate is entered and primitive roots exist, the calculator constructs and verifies one from the modulus's prime-power structure. This is not a bounded trial search.

Complete cycles of order at most $36$ use a circular diagram. Longer cycles use an exponent-versus-residue plot. Both the plot and table are capped at $k=240$, with the omitted return exponent stated beside the result.

The method depends on factoring $n$ and $\varphi(n)$. Trial-division factorization is straightforward and reliable for moderate values, but it can be slower for large allowed inputs than more advanced factorization methods.

Large modular multiplications may require exact large-integer arithmetic support in the calculation environment. If that support is unavailable, very large exact products may not be handled.

For cryptography, use this as a learning tool only. Real cryptographic parameter selection involves additional security requirements beyond simply finding a primitive root or generator.

How to Use This Calculator

Enter the modulus $n$ as an integer from $2$ to $1,000,000,000$.
Optionally enter an integer candidate $g$. Leave it blank to construct and verify a primitive root automatically when one exists.
Set the list limit from $20$ to $500$. Primitive roots are listed only when $n$ is no larger than this limit.
Use the show-powers option to show or hide the candidate's power sequence.
Review whether primitive roots exist for the modulus.
Check the candidate order. If it equals $\varphi(n)$, the candidate is primitive.
Inspect $\varphi(n)$, the factorization of $\varphi(n)$, listed roots, and power-sequence rows when they are available.
Try the example presets to compare a prime case, a no-root case, and a composite case.
If a graph is shown and download is available, use the PNG option to save the visualization.

Frequently Asked Questions

Can every modulus have a primitive root?

No. For $n\ge 2$, primitive roots exist only for $n=2$, $n=4$, odd prime powers $p^k$, and twice odd prime powers $2p^k$. A modulus such as $8$ or $12$ has units, but no single unit generates all of them.

Why must the candidate be coprime to the modulus?

Primitive roots live in the multiplicative group of units modulo $n$. A number is a unit only when it is coprime to $n$. If $\gcd(g,n)>1$, powers of $g$ cannot generate the reduced residue system.

What is the difference between order and primitive root?

The order of $g$ modulo $n$ is the length of the cycle before $g^d\equiv 1\pmod{n}$. A primitive root is a unit whose order is as large as possible, namely $\varphi(n)$. Every primitive root has an order, but not every unit with an order is primitive.

Why does the power sequence start at $k=0$?

The sequence starts at $g^0$, and $g^0\equiv 1\pmod{n}$ for any unit $g$. Starting at $k=0$ makes it clear when the cycle begins and when it returns to $1$.

Does a skipped root list mean no primitive roots exist?

No. A skipped list means $n$ is larger than the selected list limit, so the calculator did not enumerate all roots. Use the existence result and candidate-order result to understand the modulus and candidate.

Is a primitive root the same as a modular inverse?

No. A modular inverse of $g$ is a number that multiplies with $g$ to give $1$ modulo $n$. A primitive root is a unit whose powers generate every unit modulo $n$.

Sources and References

Books

William Stein. Elementary Number Theory: Primes, Congruences, and Secrets. Author-hosted edition, January 23, 2017. Sections 2.1 and 2.5 on congruences, Euler's theorem, primitive roots, and the structure of $({\mathbb Z}/p{\mathbb Z})^*$. https://wstein.org/ent/ent.pdf
Victor Shoup. A Computational Introduction to Number Theory and Algebra. Version 2.5, Cambridge University Press / author-hosted electronic version, May 16, 2008. Sections 2.6, 2.7, 7.5, and 11.1–11.3 on Euler's phi function, multiplicative order, primitive roots, generators, discrete logarithms, and Diffie-Hellman background. https://www.shoup.net/ntb/ntb-v2_5.pdf

Online and Official Sources

National Institute of Standards and Technology. “§27.2 Functions.” NIST Digital Library of Mathematical Functions, Release 1.2.7. Accessed July 4, 2026. https://dlmf.nist.gov/27.2
National Institute of Standards and Technology. “§27.16 Cryptography.” NIST Digital Library of Mathematical Functions, Release 1.2.7. Accessed July 4, 2026. https://dlmf.nist.gov/27.16