primitive root

primitive root (plural primitive roots)

1. (mathematics, number theory) For a given modulus n, a number g such that for every a coprime to n there exists an integer k such that g^k ≡ a (mod n); a generator (or primitive element) of the multiplicative group, modulo n, of integers relatively prime to n.
   • 1941, Derrick Henry Lehmer, Guide to Tables in the Theory of Numbers, National Research Council, page 13:

     There are ${\displaystyle \phi (p-1)}$ incongruent primitive roots of ${\displaystyle 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.

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

     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.

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

     For example, the prime 7 has ${\displaystyle \phi (6)=2}$ primitive roots, namely, 3 and 5. Also, the prime 11 has ${\displaystyle \phi (10)=4}$ primitive roots, namely, 2, 6, 7, 8.
     Recall from Theorem 6.7 that if ${\displaystyle m}$ has primitive roots, and if ${\displaystyle g}$ is one primitive root ${\displaystyle (\operatorname {mod} m)}$, then we can obtain all primitive roots ${\displaystyle (\operatorname {mod} m)}$ by raising ${\displaystyle g}$ to appropriate exponents.

• Often qualified, as primitive root modulo n.
• The term is used (only) in number theory, in the context of modular arithmetic, and refers to an integer modulo n (more formally, it refers to a congruence class of integers).
  • The synonyms primitive element and generator (or generating element) have broader applicability, and refer to an element of a multiplicative group.

• (number that generates other numbers modulo n): generator, primitive element

• multiplicative order

• Multiplicative group of integers modulo n on Wikipedia.Wikipedia
• Artin's conjecture on primitive roots on Wikipedia.Wikipedia
• Wilson's theorem on Wikipedia.Wikipedia
• Multiplicative order on Wikipedia.Wikipedia
• Root of unity modulo n on Wikipedia.Wikipedia
• Quadratic residue on Wikipedia.Wikipedia
• Euler's totient function on Wikipedia.Wikipedia