primitive root

Noun

primitive root (plural primitive roots)

1. For a given modulus n, a number g such that for every a coprime to n there exists an integer k such that gᵏ ≡ a (mod n); a generator (or primitive element) of the multiplicative group, modulo n, of integers relatively prime to n.
   • There are #92;phi(p-1) incongruent primitive roots of p. The fact that there are so many primitive roots causes no difficulty in the theory of the binomial congruence but has caused considerable confusion in the tabulation of primitive roots.1941, Derrick Henry Lehmer, Guide to Tables in the Theory of Numbers, National Research Council, page 13
   • The integers 2, 3, 4, and 6 each have exactly one primitive root and therefore, by default, each has a set of primitive roots consisting of "consecutive" integers.
     The integer 5, with primitive roots of 2 and 3 is the only positive integer having at least two primitive roots for which the entire...1992, Joe Roberts, Lure of the Integers, Mathematical Association of America, page 55

   Synonyms:

   generator, primitive element