Online Primitive Root Calculator

Find the primitive roots of numbers with our online calculator. Learn about primitive roots, their properties, and how to calculate them step by step.

What is a Primitive Root?

A primitive root modulo n is an integer g that is a generator of the multiplicative group of integers modulo n. In simpler terms, a primitive root g modulo n is a number whose powers modulo n produce all the integers from 1 to n-1 exactly once.

Primitive roots exist only for certain values of n. Specifically, n must be 1, 2, 4, p^k, or 2p^k, where p is an odd prime number and k is a positive integer.

Key Characteristics

For a given n, there may be multiple primitive roots
Primitive roots are used in cryptography and number theory
The order of a primitive root modulo n is n-1

Mathematical Definition

A number g is a primitive root modulo n if and only if g and n are coprime (gcd(g, n) = 1) and the smallest positive integer k such that g^k ≡ 1 mod n is k = φ(n), where φ is Euler's totient function.

How to Find a Primitive Root

Finding primitive roots involves several steps:

First, verify that n has primitive roots by checking if n is 1, 2, 4, p^k, or 2p^k
Compute φ(n) using Euler's totient function
Factorize φ(n) into its prime factors
Find a number g that is coprime with n
Check if g has order φ(n) modulo n

φ(n) = n * product over all distinct prime factors p of n of (1 - 1/p)

Algorithm Steps

The algorithm to find primitive roots typically involves:

Compute φ(n)
Factorize φ(n)
Test numbers g starting from 2 until a primitive root is found
For each g, check if g^(φ(n)/p) ≢ 1 mod n for all prime factors p of φ(n)

Properties of Primitive Roots

Primitive roots have several important properties:

They generate all numbers coprime to n through their powers
There are exactly φ(φ(n)) primitive roots modulo n
If g is a primitive root modulo n, then g^k is also a primitive root if and only if gcd(k, φ(n)) = 1

Example with n = 7

For n = 7, φ(7) = 6. The prime factors of 6 are 2 and 3. The primitive roots modulo 7 are the numbers that are not congruent to 1 modulo 7 and whose orders are 6.

Example Calculation

For n = 7, the primitive roots are 3 and 5 because:

3^1 ≡ 3 mod 7
3^2 ≡ 2 mod 7
3^3 ≡ 6 mod 7
3^4 ≡ 4 mod 7
3^5 ≡ 5 mod 7
3^6 ≡ 1 mod 7

Example Calculation

Let's find a primitive root modulo 11:

Compute φ(11) = 10
Factorize 10 = 2 × 5
Test numbers starting from 2:

2^10 ≡ 1 mod 11 (but need to check other conditions)
2^5 ≡ 10 mod 11 ≢ 1 mod 11
2^2 ≡ 4 mod 11 ≢ 1 mod 11

2 is a primitive root modulo 11

Verification

The powers of 2 modulo 11:

2^1 ≡ 2 mod 11
2^2 ≡ 4 mod 11
2^3 ≡ 8 mod 11
2^4 ≡ 5 mod 11
2^5 ≡ 10 mod 11
2^6 ≡ 9 mod 11
2^7 ≡ 7 mod 11
2^8 ≡ 3 mod 11
2^9 ≡ 6 mod 11
2^10 ≡ 1 mod 11

All numbers from 1 to 10 appear exactly once, confirming 2 is a primitive root modulo 11.

FAQ

What is the difference between a primitive root and a generator?: A primitive root is a specific type of generator in modular arithmetic. In the multiplicative group of integers modulo n, a primitive root is an element whose powers generate all other elements in the group.
How many primitive roots does a number have?: The number of primitive roots modulo n is given by φ(φ(n)), where φ is Euler's totient function. This means there are exactly φ(φ(n)) primitive roots for each n that has primitive roots.
Can every number have a primitive root?: No, primitive roots exist only for certain values of n. Specifically, n must be 1, 2, 4, p^k, or 2p^k, where p is an odd prime number and k is a positive integer.
What are the applications of primitive roots?: Primitive roots are used in various areas of mathematics and computer science, including cryptography, especially in the Diffie-Hellman key exchange algorithm, and in number theory for understanding the structure of multiplicative groups.
How can I verify if a number is a primitive root?: To verify if g is a primitive root modulo n, you need to check that g and n are coprime and that the smallest positive integer k such that g^k ≡ 1 mod n is k = φ(n).