Calculator Input
Example Data Table
| Modulus n | φ(n) | Candidate g | Primitive Root? | Smallest Root | Primitive Roots |
|---|---|---|---|---|---|
| 7 | 6 | 3 | Yes | 3 | 3, 5 |
| 9 | 6 | 2 | Yes | 2 | 2, 5 |
| 10 | 4 | 3 | Yes | 3 | 3, 7 |
| 12 | 4 | 5 | No | None | None |
Formula Used
A number g is a primitive root modulo n when its powers generate every reduced residue modulo n.
Its multiplicative order must equal φ(n).
The main test is:
g^(φ(n)/q) mod n ≠ 1
for every prime divisor q of φ(n).
Primitive roots exist only for moduli shaped like
2, 4, p^k, or 2p^k,
where p is an odd prime.
If one primitive root is known, all primitive roots are
g^k mod n
where 1 ≤ k ≤ φ(n) and gcd(k, φ(n)) = 1.
How to Use This Calculator
- Enter the modulus
n. It must be at least 2. - Enter a candidate root if you want to test one.
- Set how many primitive roots should be displayed.
- Press the calculate button.
- Read the summary above the form.
- Check the verification table for each prime factor test.
- Use CSV or PDF buttons to download the result.
Understanding Primitive Roots Modulo n
What the Calculator Does
A primitive root modulo calculator helps study repeated powers under modular arithmetic. It checks whether a base can generate every reduced residue class. This idea appears in number theory, cryptography, and algebra. The calculator first factors the modulus. It then finds Euler’s totient value. After that, it checks whether primitive roots can exist. This saves time because many moduli have no primitive roots.
Why the Totient Matters
Euler’s totient function counts integers that are coprime to the modulus. For a primitive root, the power cycle length must equal that count. So the calculator compares the order of the candidate with φ(n). If both values match, the candidate is a primitive root. If the order is smaller, the powers repeat too early. Then some residues are missing from the cycle.
Fast Verification Method
Testing every power can be slow. A faster test uses prime factors of φ(n). For each prime factor q, the calculator raises the candidate to φ(n)/q. If any result equals one, the candidate fails. If all results differ from one, the candidate passes. This method is compact and reliable for supported moduli.
Reading the Results
The result panel shows the modulus, φ(n), factorization, and root status. The verification table shows each exponent test. The power trace shows early powers of the selected base. The listed roots are generated from the smallest primitive root. The export buttons help save your calculation. They are useful for notes, assignments, and proof checking. Always review the modulus condition first. It explains why some inputs produce no primitive roots.
FAQs
1. What is a primitive root modulo n?
A primitive root modulo n is a number whose powers generate every number coprime to n. Its order equals Euler’s totient value φ(n).
2. Do all moduli have primitive roots?
No. Primitive roots exist only for 2, 4, odd prime powers, and twice odd prime powers. Other moduli do not have them.
3. Why must gcd(g, n) equal 1?
The base must be coprime to n. Otherwise, its powers cannot stay inside the reduced residue system, so it cannot generate all units.
4. What does φ(n) mean?
Euler’s totient φ(n) counts positive integers up to n that are coprime to n. A primitive root must have exactly that order.
5. How is a candidate tested?
The calculator checks g raised to φ(n)/q for every prime factor q of φ(n). The candidate passes when no residue equals one.
6. Why is my modulus rejected?
The calculator limits n to keep browser calculations practical. Very large inputs need optimized libraries or command-line tools for better speed.
7. Can negative candidates be used?
Yes. The calculator normalizes a negative candidate into its positive residue modulo n before testing its order and primitive root status.
8. Why are only some roots shown?
The display limit prevents very long pages. Increase the limit if you want more listed roots, up to the allowed maximum.