Primitive Roots

Factorization difficulty depends on the size of the factors of n and of φ(n), not just the size of the input. If a factorization is incomplete, the results that depend on it are withheld. Computation runs locally in your browser.

Primitive roots are exactly the generators of the multiplicative group of units (ℤ/nℤ)^×, so they exist exactly when this group is cyclic. That happens exactly when

So n=2 and n=4 are handled directly; if n>4 and 4 | n, there is none; otherwise n is factored and its shape is checked. Nothing is searched until existence has been established.

Assume primitive roots exist. The unit group has order φ(n), and a unit g is a generator exactly when its order is φ(n). If φ(n) = ∏ q_i^e_i, it is enough to check

for every distinct prime q_i. If one of these powers is 1, the order of g divides the proper divisor φ(n)/q_i. If none is, no proper divisor of φ(n) can be the order, so ord_n(g) = φ(n). For such moduli λ(n) = φ(n).

The calculator factors n, computes φ(n), factors φ(n) (for n = p^k or 2p^k, where φ(n) = p^(k−1)(p − 1), only p − 1 needs factoring), and tests the candidates 2,3,4,\dots in increasing order (only odd ones when n is even), skipping non-units. The first success is reported and verified.

Once g_0 is primitive, the generators of a cyclic group of order φ(n) are precisely g_0^{k} with gcd(k, φ(n)) = 1:

Therefore there are exactly φ(φ(n)) primitive roots modulo n. They are listed only when there are at most 1000 of them and φ(n) ≤ 100000.

Related: Multiplicative Order · Euler Totient · Carmichael Function · Modular Exponentiation · Prime Factorization