Primitive Root

Also found in: Wikipedia.

primitive root

[′prim·əd·iv ′rüt]
An n th root of unity that is not an m th root of unity for any m less than n.

Primitive Root


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 Primitive Root, where k is the number of distinct prime divisors of ρ — 1.


Vinogradov, I. M. Osnovy teorii chisel, 8th ed. Moscow, 1972.
Vinogradov, I. M. Izbr. trudy. Moscow, 1952. Pages 54–57.
References in periodicals archive ?
min] corresponding to primitive root of the codes as follows:
Smarandache function, divisibility, primitive root.
To get a period of maximal length m - 1, m must be a prime; a is a primitive root of m; and [x.
n](a) = [phi](n), we say that a is a primitive root (mod n).
32] - 2 for any odd primitive root a of the prime [2.
Let c be a primitive root for r, let [chi] be a character of order n defined by [chi](c) = [omega] where [omega] = [e.
p) denote the smallest square-free primitive root modulo p.
m-1 mod m = 1 (7) and a standard number theoretic definition: If m is prime then a is a primitive element modulo m (or primitive root of m) iff a.
n-1] for all n [greater than or equal to] 1 if l is a primitive root modulo [p.
The number of the primitive roots of the congruence t3 = 1mod p is two.
Archery may have primitive roots, but "primitive" is hardly the adjective I'd use to describe modern bowhunting.
Trevor-Roper argues that the unavoidable contrast between their experiences of continental cosmopolitanism and their own primitive roots, coupled with the reading of Montesquieu's Spirit of the Laws, account for a near obsession with the causes of social progress among Scots intellectuals from David Hume through William Robertson, Adam Ferguson, Adam Smith, and John Millar.