Lesson plan

Primitive root modulo n

In number theory, a number is a primitive root modulo if every number coprime to is congruent to a power of modulo . In symbols, is a primitive root modulo if for every integer coprime to , there is some integer for which . Primitive roots only exist for some integers . Specifically, a primitive root exists modulo if and only if is 4, or for some odd prime number and some . This was first proved by Carl Friedrich Gauss. Gauss defined primitive roots in Article 57 of his Disquisitiones Arithmeticae (1801), where he credited Leonhard Euler with coining the term. In Article 56 he stated that Johann Heinrich Lambert and Euler knew of them, but he was the first to rigorously demonstrate that primitive roots exist for a prime number . In fact, the Disquisitiones contains two proofs: The one in Article 54 is a nonconstructive existence proof, while the proof in Article 55 is constructive. An equivalent characterization is that is a primitive root modulo if and only if is a generator of the multiplicative group of integers modulo . Thus, primitive roots exist if and only if this group is a cyclic group. If is a primitive root modulo and , then the value is called the index or discrete logarithm of to the base modulo .

Back to article

Article summary

In number theory, a number is a primitive root modulo if every number coprime to is congruent to a power of modulo . In symbols, is a primitive root modulo if for every integer coprime to , there is some integer for which . Primitive roots only exist for some integers . Specifically, a primitive root exists modulo if and only if is 4, or for some odd prime number and some . This was first proved by Carl Friedrich Gauss. Gauss defined primitive roots in Article 57 of his Disquisitiones Arithmeticae (1801), where he credited Leonhard Euler with coining the term. In Article 56 he stated that Johann Heinrich Lambert and Euler knew of them, but he was the first to rigorously demonstrate that primitive roots exist for a prime number . In fact, the Disquisitiones contains two proofs: The one in Article 54 is a nonconstructive existence proof, while the proof in Article 55 is constructive. An equivalent characterization is that is a primitive root modulo if and only if is a generator of the multiplicative group of integers modulo . Thus, primitive roots exist if and only if this group is a cyclic group. If is a primitive root modulo and , then the value is called the index or discrete logarithm of to the base modulo .

Key claims

No claims recorded.

Discussion questions

  1. Summarise the article in your own words. Which single claim would you verify first, and why?
  2. Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
  3. If two sources disagreed about one of these facts, what would you need in order to trust one over the other?

Bibliography

No sources recorded.

Key claims and bibliography are generated from the same tracked claims and sources as the article page.