# Primitive Root

Also found in: Wikipedia.

## primitive root

[′prim·əd·iv ′rüt]*n*th root of unity that is not an

*m*th root of unity for any

*m*less than

*n*.

*The Great Soviet Encyclopedia*(1979). It might be outdated or ideologically biased.

## Primitive Root

A primitive root modulo m is a number *g* such that the smallest positive number *k* for which the difference *g ^{k}* — 1 is divisible by

*m*—that is, for which

*g*is congruent to 1 modulo

^{k}*m*—coincides with ɸ(m), where ɸ(m) is the number of positive integers less than

*m*and relatively prime to

*m.*For example, if

*m*= 7, the number 3 is a primitive root modulo 7. In fact, ɸ(7) = 6, since the numbers 3

^{1}– 1 = 2, 3

^{2}– 1 = 8, 3

^{3}- 1 = 26, 3

^{4}- 1 = 80, and 3

^{5}- 1 = 242 are not divisible by 7—only 3

^{6}— 1 = 728 is divisible by 7. Primitive roots exist only for

*m*= 2,

*m*= 4,

*m = p*and

^{a},*m = 2p*where

^{a},*ρ*is an odd prime and α is a positive integer. The number of primitive roots in these cases is equal to ɸ[ɸ(m)] (numbers whose difference is divisible by

*m*are not considered distinct). In 1926, 1. M. Vinogradov showed that a primitive root modulo

*p,*where

*ρ*is an odd prime, can be found in the interval , where

*k*is the number of distinct prime divisors of

*ρ*— 1.

### REFERENCES

Vinogradov, I. M.*Osnovy teorii chisel,*8th ed. Moscow, 1972.

Vinogradov, I. M.

*Izbr. trudy.*Moscow, 1952. Pages 54–57.