primitive root
English
Noun
primitive root (plural primitive roots)
- (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 gk ≡ 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 incongruent primitive roots of . 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 primitive roots, namely, 3 and 5. Also, the prime 11 has primitive roots, namely, 2, 6, 7, 8.
- Recall from Theorem 6.7 that if has primitive roots, and if is one primitive root , then we can obtain all primitive roots by raising to appropriate exponents.
- 1941, Derrick Henry Lehmer, Guide to Tables in the Theory of Numbers, National Research Council, page 13,
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 gk ≡ a (mod n) exists for every a coprime to n — see also generator, primitive element
|
See also
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