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^k 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 3¹ – 1 = 2, 3² – 1 = 8, 3³ - 1 = 26, 3⁴ - 1 = 80, and 3⁵ - 1 = 242 are not divisible by 7—only 3⁶ — 1 = 728 is divisible by 7. Primitive roots exist only for m = 2, m = 4, m = p^a, and m = 2p^a, 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.