primitive root

plural primitive roots

1. mathematicsFor 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

   2 more examples

   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 set of primitive roots are consecutive integers.

   1992, Joe Roberts, Lure of the Integers, Mathematical Association of America, page 55

   For example, the prime 7 has #92;phi(6)#61;2 primitive roots, namely, 3 and 5. Also, the prime 11 has #92;phi(10)#61;4 primitive roots, namely, 2, 6, 7, 8. Recall from Theorem 6.7 that if m has primitive roots, and if g is one primitive root (#92;operatorname#123;mod#125;m), then we can obtain all primitive roots (#92;operatorname#123;mod#125;m) by raising g to appropriate exponents.

   2006, Neville Robbins, Beginning Number Theory, Jones & Bartlett Learning, page 159

   Synonyms: generator, primitive element