Input parameters
Enter a prime modulus and optional candidate base. You can also request a full list of primitive roots and a short sequence of powers.
Formula used
For a prime modulus p, the nonzero residues modulo p form a multiplicative group of order p − 1. The multiplicative order of an integer g modulo p is defined as:
ordp(g) = smallest k ≥ 1 such that g^k ≡ 1 (mod p).
-
Compute φ = p − 1 and factor it as
φ = ∏ qiei. -
g is a primitive root modulo p if and only if
ordp(g) = p − 1. -
Equivalently, for each prime factor q of p − 1,
g(p−1)/q ≢ 1 (mod p). - The calculator uses this criterion and the factorization of p − 1 to test primitive roots efficiently.
How to use this calculator
- Enter a prime modulus p greater than 2 in the first field.
- Optionally enter an integer candidate g to test as a primitive root modulo p.
- Tick “List all primitive roots modulo p” if you need the complete set of generators.
- Tick “Show powers of the smallest primitive root” to see the generated sequence of residues.
- Press “Compute” to view the smallest primitive root, candidate analysis, and optional full list.
- Use the “Download CSV” and “Download PDF” buttons above the results table to export data for documentation or further study.
Example of using primitive root calculator
Consider the prime modulus p = 11. We want to check whether g = 2 is a primitive root modulo 11 and see how the calculator presents the results.
- Enter 11 in the field “Prime modulus p”.
- Enter 2 in the field “Candidate base g”.
- Optionally tick “List all primitive roots modulo p” to see every generator.
- Click the Compute button to run the analysis.
The calculator computes p − 1 = 10 and factors it as
10 = 2 × 5. It then checks:
210/2 = 25 ≡ 10 (mod 11) ≠ 1210/5 = 22 ≡ 4 (mod 11) ≠ 1
Since these powers never give 1, the calculator concludes that
g = 2 is a primitive root modulo 11 and reports
ord11(2) = 10 in the results table.
If you also tick “List all primitive roots modulo p”, you will see the other generators modulo 11 listed together with g = 2.
Example data table
These examples illustrate primitive roots for small primes. You can reproduce them by entering the same primes and options above.
| Prime p | p − 1 | Factorization of p − 1 | Number of primitive roots | Smallest primitive root | Sample primitive roots |
|---|---|---|---|---|---|
| 7 | 6 | 2 × 3 | 2 | 3 | 3, 5 |
| 11 | 10 | 2 × 5 | 4 | 2 | 2, 6, 7, 8 |
| 13 | 12 | 22 × 3 | 4 | 2 | 2, 6, 7, 11 |
| 17 | 16 | 24 | 8 | 3 | 3, 5, 6, 7, 10, 11, 12, 14 |
Frequently asked questions
1. What is a primitive root modulo a prime?
A primitive root modulo a prime p is an integer g whose powers generate every nonzero residue modulo p. That means the set g^1, g^2, …, g^(p−1) modulo p hits all values from 1 to p−1.
2. How does this calculator test primitive roots?
The calculator factors p − 1 into prime powers, then checks g^((p−1)/q) mod p for every distinct prime factor q. If any result equals 1, g is rejected as a primitive root.
3. Can I use this tool for composite moduli?
This calculator is designed specifically for prime moduli. It first verifies that p is prime. If p is composite, it shows an error message and does not attempt to compute primitive roots or orders.
4. Why is listing all primitive roots limited?
Listing every primitive root requires checking many candidates. For performance reasons, this tool restricts the “list all primitive roots” option to primes up to 50,000. For larger primes, only the smallest primitive root and candidate analysis are computed.
5. What does the order column represent?
The order ord_p(g) is the smallest positive exponent k such that g^k ≡ 1 (mod p). If the order equals p − 1, g is a primitive root and generates the multiplicative group.
6. Can I enter negative or large candidate bases?
Yes. The calculator automatically reduces any integer g modulo p before testing. Negative inputs and values greater than p are normalized into the range 1,…,p−1 so that primitive root checks behave consistently.
7. How do I export results for documentation?
Use the CSV and PDF buttons above the results table. CSV exports a comma-separated file for spreadsheets, while PDF creates a simple text table layout suitable for printing, sharing with students, or attaching to notes.