primitive root calculator

What this primitive root calculator does

This tool computes key number theory facts for modular arithmetic:

• Prime factorization of n
• Euler's totient value φ(n)
• Whether primitive roots exist modulo n
• The number of primitive roots (when they exist)
• A list of primitive roots modulo n
• Optional verification for your chosen candidate g

If no primitive root exists for your modulus, the calculator clearly reports that too.

What is a primitive root?

Definition

A number g is a primitive root modulo n if every number coprime to n can be written as a power of g modulo n. Equivalently, g has multiplicative order φ(n).

For example, modulo 7, the number 3 is a primitive root because powers of 3 generate all non-zero residues modulo 7:

31 = 3, 32 = 2, 33 = 6, 34 = 4, 35 = 5, 36 = 1 (mod 7)

When primitive roots exist

Primitive roots modulo n exist only for the following forms:

• n = 2
• n = 4
• n = p^k where p is an odd prime
• n = 2p^k where p is an odd prime

So values like 8, 12, 15, and 24 have no primitive roots, while 5, 9, 14, and 18 do.

How the calculator works

Step 1: Compute φ(n)

The tool factors n and computes Euler's totient function. This gives the size of the multiplicative group modulo n.

Step 2: Test primitive root existence

Using the characterization above, it first determines whether primitive roots can exist for your modulus.

Step 3: Verify generator condition

For each coprime candidate g, the calculator checks whether g^φ(n)/q ≠ 1 (mod n) for every prime divisor q of φ(n). If true, g is a primitive root.

Examples to try

• n = 17 → primitive roots exist, and there are several generators.
• n = 9 → primitive roots exist (for example 2 and 5).
• n = 12 → no primitive roots exist.
• n = 14 → primitive roots exist; great practice case.

Why primitive roots matter

Primitive roots appear in many areas of mathematics and computation:

• Public-key cryptography (discrete logarithms and key exchange)
• Pseudorandom sequence generation
• Fast transforms in modular arithmetic
• Abstract algebra and elementary number theory education

If you are studying modular arithmetic, this calculator is a quick way to confirm homework, explore examples, and build intuition.