Also found in: Wikipedia.
primitive root[′prim·əd·iv ′rüt]
A primitive root modulo m is a number g such that the smallest positive number k for which the difference gk — 1 is divisible by m—that is, for which gk is congruent to 1 modulo 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 31 – 1 = 2, 32 – 1 = 8, 33 - 1 = 26, 34 - 1 = 80, and 35 - 1 = 242 are not divisible by 7—only 36 — 1 = 728 is divisible by 7. Primitive roots exist only for m = 2, m = 4, m = pa, and m = 2pa, where ρ 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.
REFERENCESVinogradov, I. M. Osnovy teorii chisel, 8th ed. Moscow, 1972.
Vinogradov, I. M. Izbr. trudy. Moscow, 1952. Pages 54–57.