Metraipolis › archive › dc_ae7e8dbbd12f

Primitive root modulo n — Wikipedia (en)

Source
Wikipedia (en)
Original
https://en.wikipedia.org/wiki/Primitive_root_modulo_n
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-07T22:54:52.070Z
SHA-256 of the archived text
8f6c8db517a25511765fbc34fa05a4ba1a2787ea765cd972498af56168e32761
Stable URL of this page
https://metraipolis.com/documento/dc_ae7e8dbbd12f

How to cite

Primitive root modulo n — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Primitive_root_modulo_n (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_ae7e8dbbd12f (Metraipolis archive dc_ae7e8dbbd12f, sha256 8f6c8db517a25511765fbc34fa05a4ba1a2787ea765cd972498af56168e32761)
BibTeX
@misc{dcae7e8dbbd12f,
  title = {Primitive root modulo n — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/Primitive_root_modulo_n},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_ae7e8dbbd12f; sha256 8f6c8db517a25511765fbc34fa05a4ba1a2787ea765cd972498af56168e32761},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Primitive_root_modulo_n. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

In number theory, a number g is a primitive root modulo n if every number a coprime to n is congruent to a power of g modulo n. In symbols, g is a primitive root modulo n if for every integer a coprime to n, there is some integer k for which gk ≡ a (mod n). Primitive roots only exist for some integers n. Specifically, a primitive root exists modulo n if and only if n is 4, pk or 2pk for some odd prime number p and some k ≥ 0. 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 n. 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 g is a primitive root modulo n if and only if g is a generator of the multiplicative group of integers modulo n. Thus, primitive roots exist if and only if this group is a cyclic group. If g is a primitive root modulo n and gk ≡ a (mod n), then the value k is called the index or discrete logarithm of a to the base g modulo n.

Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «number theory»).
Fonte: Wikipedia in inglese, voce «Primitive root modulo n» — https://en.wikipedia.org/wiki/Primitive_root_modulo_n
Wikidata Q948010 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q948010
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Primitive_root_modulo_n?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1378646607, consultata il 2026-10-07T22:31:36.680Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: cac6c292cedd83cde20b5fa007219875f070662d1210167506dabb6b0e3cb813