A primitive element here means a generator of the multiplicative group of units modulo n. For prime n, it matches the usual primitive root concept.
These examples show common moduli and known primitive elements. Try them in the calculator to verify outputs.
| Example modulus n | φ(n) | Sample primitive elements | Notes |
|---|---|---|---|
| 17 | 16 | 3, 5, 6, 7, 10, 11, 12, 14 | Prime modulus; total primitive elements = φ(16)=8. |
| 9 | 6 | 2, 5 | Odd prime power; total primitive elements = φ(6)=2. |
| 14 | 6 | 3, 5 | 2·p where p is odd prime; generators exist. |
- Euler totient: φ(n) counts integers in {1,…,n} that are coprime to n. If n = ∏ pᵢ^{eᵢ}, then φ(n) = n · ∏ (1 − 1/pᵢ).
- Primitive element test: Let m = φ(n), and let q run over the prime divisors of m. A candidate g is primitive if g^(m/q) ≠ 1 (mod n) for every such q.
- Total count (when it exists): The number of primitive elements modulo n is φ(φ(n)).
- Enter the modulus n you want to analyze.
- Keep Auto mode unless you need a specific mode.
- Set a reasonable candidate range and a test cap for performance.
- Click Find primitive elements to compute results.
- Use the download buttons to export your current result set.
Why Primitive Elements Matter in Modular Arithmetic
In many number theory tasks you need an element whose powers visit every nonzero residue that is coprime to n. Such a generator makes discrete exponent tables predictable, supports indexing of residues, and simplifies proofs about orders and cyclic subgroups. For a prime modulus p, primitive elements generate the nonzero field elements, so one generator produces all p−1 residues by repeated multiplication. In cryptography, generators support Diffie–Hellman style exponentiation and uniform sampling over U(n) efficiently securely.
When Generators Exist: Practical Screening Rules
The unit group U(n) is cyclic only for n equal to 2, 4, p^k, or 2·p^k with odd prime p. This calculator checks that condition in Auto mode before searching. For example, n=17, n=9, and n=14 admit primitive elements, while n=8 and n=12 do not. If generators do not exist, the tool still reports φ(n) and factorizations for quick diagnostics.
Computation Workflow Implemented in the Tool
The process begins by factoring n using trial division, then computing Euler’s totient φ(n). Next, φ(n) is factored and only its distinct prime divisors are retained. A candidate g is accepted when gcd(g,n)=1 and, for every prime q dividing φ(n), the modular power g^(φ(n)/q) is not congruent to 1 (mod n). This standard test avoids enumerating all powers of g.
Reading Results: Orders, Counts, and Exports
When primitive elements exist, every listed g has order exactly φ(n), so the Order column matches φ(n) by design. The theoretical number of primitive elements equals φ(φ(n)), shown beside your run statistics. CSV export lists each primitive element with its order, while the PDF report summarizes inputs, timing, and the same generator test, making it suitable for assignments and documentation.
Performance Controls and Verification Tips
Search cost depends on the candidate range and the number of prime factors of φ(n). Use a narrow range first, enable “find only the first” to get one generator quickly, then expand if you need a longer list. The Max candidates cap prevents excessive runtimes for large n. To verify a reported generator, confirm that g^(φ(n)/q) ≠ 1 (mod n) for each prime q|φ(n), and optionally spot-check that powers of g cover many residues.
1) What is a primitive element modulo n?
It is a unit g whose powers generate every value that is coprime to n. Equivalently, g has multiplicative order φ(n) in U(n).
2) Why do some moduli show that primitive elements are not available?
Generators exist only when the unit group is cyclic: n equals 2, 4, p^k, or 2·p^k with odd prime p. For other n, no single g generates all units.
3) How does the calculator compute φ(n)?
It factors n and applies φ(n)=n·∏(1−1/p) over distinct prime divisors p. This is reliable for all positive n and avoids listing coprime residues one by one.
4) Why is the test based on g^(φ(n)/q) not equaling 1?
If g had smaller order, that order would divide φ(n), so g^(φ(n)/q)=1 for some prime divisor q of φ(n). Failing this condition for every q forces the full order φ(n).
5) How can I make the search faster for larger n?
Start the candidate range near 2, enable “find only the first”, and keep the results limit small. Raising Max candidates increases coverage but also time; use it only when needed.
6) For prime n, is this the same as finding primitive roots?
Yes. When n is prime, U(n) has size n−1 and is cyclic, so any primitive element is a primitive root modulo n. The tool simply generalizes the same idea to valid composite moduli.