Math 2.0

Number theory Theorem

Primitive root theorem

Builds on Primitive root modulo nExistence of primitive roots modulo a prime

Statement

Let nn be an integer with n≥2n \ge 2. There is a primitive root modulo nn if and only if n∈{2,4,pk,2pk}n \in \{2, 4, p^k, 2p^k\}. Here pp is an odd prime and kk is a positive integer.

Remarks

Equivalently, the group (ℤ/nℤ)×(\mathbb{Z}/n\mathbb{Z})^\times is cyclic exactly for these nn. The case n=pn = p is the existence of primitive roots modulo a prime. For example, there are primitive roots modulo 99, 1818 and 2525, but not modulo 88, 1212 or 1515.

History

Carl Friedrich Gauss gave the first proof. He defined primitive roots in his Disquisitiones Arithmeticae of 1801.

Reading path

To understand this page from the ground up, read these 11 pages in order. The foundations come first.

Show the path as a graph
Divisibility, definition, no evidence levelDivisibilitydefinitionCongruence modulo n, definition, no evidence levelCongruence modulo ndefinitionGreatest common divisor, definition, no evidence levelGreatest common divis…definitionPrime number, definition, no evidence levelPrime numberdefinitionCoprime integers, definition, no evidence levelCoprime integersdefinitionEuler's totient function, definition, no evidence levelEuler's totient funct…definitionEuler's theorem, statement, no evidence levelEuler's theoremstatementMultiplicative order, definition, no evidence levelMultiplicative orderdefinitionPrimitive root modulo n, definition, no evidence levelPrimitive root modulo…definitionExistence of primitive roots modulo a prime, statement, no evidence levelExistence of primitiv…statementPrimitive root theorem, statement, no evidence levelPrimitive root theoremstatement
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Divisibility definition
  2. Congruence modulo n definition
  3. Greatest common divisor definition
  4. Prime number definition
  5. Coprime integers definition
  6. Euler's totient function definition
  7. Euler's theorem statement
  8. Multiplicative order definition
  9. Primitive root modulo n definition
  10. Existence of primitive roots modulo a prime statement
  11. Primitive root theorem statement

Further reading

  1. Web https://en.wikipedia.org/wiki/Primitive_root_modulo_n, Definition
About this page
Tag0E0DNQK22P
URIm2://0E0DNQK22P
Kindstatement, theorem
WritingW0 stub
MSC11A07
StatusThis copy of the site has no build data. Run m2 status 0E0DNQK22P.
UsesPrimitive root modulo n, Existence of primitive roots modulo a prime

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.