Primitive Root Calculator Online

Primitive roots are fundamental in number theory and cryptography. This calculator helps you find primitive roots of numbers efficiently. Learn about their properties and how to calculate them.

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 numbers 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.

For example, 3 is a primitive root modulo 7 because the powers of 3 modulo 7 are: 3^1 ≡ 3, 3^2 ≡ 2, 3^3 ≡ 6, 3^4 ≡ 4, 3^5 ≡ 5, 3^6 ≡ 1.

How to Find a Primitive Root

Finding a primitive root involves checking the powers of potential candidates modulo n until you find one that generates all numbers from 1 to n-1.

Step-by-Step Method

Factorize n-1 into its prime factors.
Select a candidate g between 2 and n-1.
Check if g^( (n-1)/p ) mod n ≠ 1 for every prime factor p of n-1.
If the condition is satisfied for all prime factors, g is a primitive root modulo n.

Formula: g is a primitive root modulo n if g^( (n-1)/p ) mod n ≠ 1 for all prime factors p of n-1.

Properties of Primitive Roots

Primitive roots have several important properties:

There are exactly φ(n-1) primitive roots modulo n, where φ is Euler's totient function.
If g is a primitive root modulo n, then g^k is also a primitive root modulo n if and only if k is coprime with φ(n).
Primitive roots can be used in cryptographic systems like the Diffie-Hellman key exchange.

Example Calculation

Let's find a primitive root modulo 7:

Factorize 6 (7-1): 6 = 2 × 3.
Check g=3:
- 3^(6/2) mod 7 = 3^3 mod 7 = 27 mod 7 = 6 ≠ 1
- 3^(6/3) mod 7 = 3^2 mod 7 = 9 mod 7 = 2 ≠ 1
Since both conditions are satisfied, 3 is a primitive root modulo 7.

Other primitive roots modulo 7 are 5 and 6.

FAQ

What is the difference between a primitive root and a generator?

In number theory, the terms "primitive root" and "generator" are often used interchangeably. Both refer to an element that generates the multiplicative group modulo n.

How many primitive roots does a number have?

The number of primitive roots modulo n is given by φ(n-1), where φ is Euler's totient function. For example, modulo 7, there are φ(6) = 2 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 and k is a positive integer.