primitive root

English

Noun

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 $\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.

   • 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 $\phi (6)=2$ primitive roots, namely, 3 and 5. Also, the prime 11 has $\phi (10)=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 $(\operatorname {mod} m)$, then we can obtain all primitive roots $(\operatorname {mod} m)$ by raising $g$ to appropriate exponents.

Usage notes

• 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.

Synonyms

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

Translations

number such that g^k ≡ a (mod n) exists for every a coprime to n — see also generator,‎ primitive element

• Chinese:

  Mandarin: 原根 (yuángēn)

• Finnish: primitiivinen juuri
• French: racine primitive f
• German: Primitivwurzel f
• Icelandic: frumstæð rót f
• Italian: radice primitiva f

See also

• multiplicative order

Further reading

• 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