# Primitive root

## Contents

## Definition

Suppose is a natural number such that the multiplicative group modulo , i.e., the group , is a cyclic group. (This happens if and only if is of one of these four forms: , where is a prime number and . Then, a **primitive root** modulo is a residue class modulo that generates the cyclic group.

We often use the term **primitive root** for an integer representative of such a residue class.

The number of primitive roots modulo , if the multiplicative group is cyclic, is where is the Euler totient function. This is because the order of the multiplicative group is , and the number of generators of a cyclic group equals the Euler phi-function of its order.

For a proof of the characterization of natural numbers for which the multiplicative group is cyclic, see Classification of natural numbers for which the multiplicative group is cyclic.

## Particular cases

### Number of primitive roots

Here are the particular cases:

Value of | Number of primitive roots |
---|---|

2 | 1 |

4 | 1 |

(odd prime) | |

, odd, | |

, odd | |

, odd, |

### Values of primitive roots

For an odd prime , any number that is a primitive root modulo continues to be a primitive root modulo higher powers of . We thus list primitive roots only for numbers of the form and .

Value of | Number of primitive roots | Smallest absolute value primitive root ( to ) | Smallest positive primitive root | All primitive roots from to |
---|---|---|---|---|

2 | 1 | 1 | 1 | 1 |

3 | 1 | -1 | 2 | 2 |

4 | 1 | -1 | 3 | 3 |

5 | 2 | 2,-2 | 2 | 2,3 |

7 | 2 | -2 | 3 | 3,5 |

9 | 2 | 2 | 2 | 2,5 |

11 | 4 | 2 | 2 | 2,6,7,8 |

13 | 4 | 2 | 2 | 2,6,7,11 |

17 | 8 | 3,-3 | 3 | 3,5,6,7,10,11,12,14 |

## Relation with other properties

### Smallests

- Smallest primitive root is the smallest positive number that is a primitive root modulo a given number.
- Smallest magnitude primitive root is the primitive root with the smallest absolute value.

- Quadratic nonresidue is a number relatively prime to the modulus that is not a square modulo the modulus. Any primitive root must be a quadratic nonresidue except in the case where the modulus is . This is because the multiplicative group has even order and hence its generator cannot be a square.

## Facts

### Known facts

For most primes, finding a primitive root is hard work. However, for those primes where has a very small list of prime factors, it is relatively easy to find a primitive root. Some cases are below:

Statement | Applicable prime type | Description in terms of factorization of |
---|---|---|

Quadratic nonresidue that is not minus one is primitive root for safe prime | safe prime | is twice of a prime. The prime is called a Sophie Germain prime. |

Safe prime has plus or minus two as a primitive root | safe prime | is twice of a prime. The prime is called a Sophie Germain prime. |

Quadratic nonresidue equals primitive root for Fermat prime | Fermat prime | power of 2. In fact, it is a power of a power of 2 |

Fermat prime greater than three implies three is primitive root | Fermat prime | power of 2. In fact, it is a power of a power of 2, and from the given condition, it is also 1 mod 4. |

### Conjectures and conditionally known facts

Artin's conjecture on primitive roots states that any integer that is not a perfect square and that is not equal to -1 occurs as a primitive root for infinitely many primes. The conjecture is open, but partial results are known:

Name of conjecture/fact | Statement | Conditional to ... |
---|---|---|

Hooley's theorem | Artin's conjecture holds for all | (special cases of) generalized Riemann hypothesis |

Gupta-Ram Murty theorem | Artin's conjecture holds for infinitely many | Unconditional |

Heath-Brown theorem on Artin's conjecture | Artin's conjecture holds for all but two exceptional values of . However, no explicit information about the explicit values of | Unconditional |