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:
“The inability to control our children’s behavior feels the same as not being able to control it in ourselves. And the fact is that primitive behavior in children does unleash primitive behavior in mothers. That’s what frightens mothers most. For young children, even when out of control, do not have the power to destroy their mothers, but mothers who are out of control feel that they may destroy their children.”
—Elaine Heffner (20th century)
“Not marble nor the gilded monuments
Of princes shall outlive this powerful rime;
But you shall shine more bright in these contents
Than unswept stone, besmeared with sluttish time.
When wasteful war shall statues overturn,
And broils root out the work of masonry,
Nor Mars his sword nor war’s quick fire shall burn
The living record of your memory.”
—William Shakespeare (1564–1616)