Primitive Root Modulo n
In modular arithmetic, a branch of number theory, a primitive root modulo n is any number g with the property that any number coprime to n is congruent to a power of g modulo n. In other words, g is a generator of the multiplicative group of integers modulo n. That is, for every integer a coprime to n, there is an integer k such that gk ≡ a (mod n). Such k is called the index or discrete logarithm of a to the base g modulo n.
Gauss defined primitive roots in Article 57 of the Disquisitiones Arithmeticae (1801), where he credited Euler with coining the term. In Article 56 he stated that Lambert and Euler knew of them, but he was the first to rigorously demonstrate that primitive roots exist. In fact, the Disquisitiones contains two proofs: the one in Article 54 is a nonconstructive existence proof, while the other in Article 55 is constructive.
Read more about Primitive Root Modulo n: Elementary Example, Definition, Examples, Finding Primitive Roots, Order of Magnitude of Primitive Roots, Applications
Famous quotes containing the words primitive and/or root:
“Not only do our wives need support, but our children need our deep involvement in their lives. If this period [the early years] of primitive needs and primitive caretaking passes without us, it is lost forever. We can be involved in other ways, but never again on this profoundly intimate level.”
—Augustus Y. Napier (20th century)
“The bud of the apple is desire, the down-falling gold,
The catbird’s gobble in the morning half-awake
These are real only if I make them so. Whistle
For me, grow green for me and, as you whistle and grow green,
Intangible arrows quiver and stick in the skin
And I taste at the root of the tongue the unreal of what is real.”
—Wallace Stevens (1879–1955)