AlsPrimitivwurzeln werden in derZahlentheorie, einemTeilgebiet der Mathematik, bestimmte Elemente vonprimen Restklassengruppen bezeichnet. Die definierende Eigenschaft einer Primitivwurzel ist, dass jedes Element der primen Restklassengruppe als eine ihrerPotenzen dargestellt werden kann.

Die Zahl 3 ist eine Primitivwurzel modulo 7, da gilt

Es lassen sich also alle Elemente${\displaystyle 1,2,\dots ,6}$ der primen Restklassengruppe modulo 7 als Potenzen${\displaystyle 3^i}$ von 3 darstellen, wobei der Exponent${\displaystyle i}$ der dem jeweiligen Element zugeordneteIndex (diskreter Logarithmus) ist. Die Zahl 2 istkeine Primitivwurzel modulo 7, da${\displaystyle 2^3=8\equiv 1(\text{mod }7)}$ ist, daher wiederholen sich die Reste in der Folge der Potenzen von 2 modulo 7

${\displaystyle (2^k{)}_{k\in \mathbb{N}}=(2^1\not\equiv 1,2^2\not\equiv 1,2^3\equiv 1,2^4\equiv 2,2^5\equiv 2^2\dots )}$

bereits nach jeweils 3 Schritten, daher werden nicht alle 6 verschiedenen primen Reste modulo 7 erreicht und 2 erzeugt die prime Restklassengruppenicht.

Eine ganze Zahl${\displaystyle a}$ ist eine Primitivwurzel modulo${\displaystyle m}$, wenn dieRestklasse${\displaystyle a+m\mathbb{Z}}$ dieprime Restklassengruppe${\displaystyle (\mathbb{Z}/m\mathbb{Z}{)}^{\times }}$erzeugt. Dies ist gleichbedeutend damit, dass eine ganze Zahl${\displaystyle a}$ genau dann eine Primitivwurzel modulo${\displaystyle m}$ ist, wenn die Ordnung von${\displaystyle a}$ modulo${\displaystyle m}$ gleich der Gruppenordnung der primen Restklassengruppe ist:

${\displaystyle {\mathrm{ord}}_m(a)=\phi (m)}$.

Hierbei ist${\displaystyle \phi }$ dieEulersche φ-Funktion und${\displaystyle {\mathrm{ord}}_m(a)}$ diemultiplikative Ordnung modulom des Elements${\displaystyle a}$, d. h. der kleinste positive Exponent${\displaystyle n}$, für welchen${\displaystyle a^n\equiv 1(\text{mod }m)}$ ist (für die Schreibweise „mod“ sieheModulo).

Genau dann ist übrigens auch

${\displaystyle {\mathrm{ord}}_m(a)=\lambda (m)}$,

wobei${\displaystyle \lambda }$ dieCarmichael-Funktion ist.^[1]

Es gibt genau dann Primitivwurzeln modulo${\displaystyle m}$, wenn die prime Restklassengruppe${\displaystyle (\mathbb{Z}/m\mathbb{Z}{)}^{\times }}$ einezyklische Gruppe ist. Dies ist nach einem Satz vonC. F. Gauß genau dann der Fall, wenn für den Modul

gilt. Dabei bezeichnet${\displaystyle \mathbb{P}}$ die Menge der Primzahlen.^[2][3]

Wenn modulo${\displaystyle m}$ Primitivwurzeln existieren, dann existieren genau${\displaystyle \phi (\phi (m))}$ modulo${\displaystyle m}$ inkongruente Primitivwurzeln. Jede dieser Primitivwurzeln ist modulo${\displaystyle m}$ kongruent zu einem Element der Menge:

${\displaystyle \{a^n\mid 1\le n\le \phi (m),\mathrm{ggT}(n,\phi (m))=1\}}$

wobei${\displaystyle a}$ eine beliebige Primitivwurzel modulo${\displaystyle m}$ ist.

Um festzustellen, ob eine Zahl${\displaystyle a}$ Primitivwurzel modulo${\displaystyle m}$ ist, wird zuerst${\displaystyle \phi (m)}$ und anschließend die Ordnung von${\displaystyle a}$ berechnet. Die Ordnung lässt sich beispielsweise bestimmen, indem nacheinander die Werte${\displaystyle a^t(\text{mod }m)}$ für${\displaystyle t\in \{1,2,\dots ,m-1\}}$ berechnet werden. Das erste${\displaystyle t}$, für das${\displaystyle a^t(\text{mod }m)=1}$ gilt, ist die Ordnung von${\displaystyle a}$.

Beim Beispiel aus der Einleitung sieht man, dass die 3 die Ordnung 6 hat. Da zudem${\displaystyle \phi (7)=6}$ gilt, ist 3 eine Primitivwurzel modulo 7.

Eine Zahl, die keine Primitivwurzel modulo 7 ist, ist die 4. Hier gilt

${\displaystyle 4^1\equiv 4(\mathrm{mod}7)}$

${\displaystyle 4^2\equiv 2(\mathrm{mod}7)}$

${\displaystyle 4^3\equiv 1(\mathrm{mod}7)}$

Die Ordnung von 4 ist deshalb 3 und die 4 keine Primitivwurzel modulo 7.

Man kann viele Versuche sparen, indem man die Tatsache benutzt, dass die Ordnung nach demSatz von Lagrange${\displaystyle \phi (m)}$ teilt, da jede Zahl${\displaystyle k\in \mathbb{N}}$, für die${\displaystyle a^k\equiv 1(\text{mod }m)}$ gilt, durch die Ordnung teilbar ist. Darum muss man nur noch für alle Teiler von${\displaystyle \phi (m)}$ überprüfen, ob Exponentiation mit ihnen die Zahl auf 1 abbildet, und der kleinste solche Teiler ist die Ordnung.

Die primen Restklassengruppen zu Moduln${\displaystyle m}$, diePrimzahlen sind, bestehen aus genau${\displaystyle m-1}$ Elementen. Die Zahlen${\displaystyle 1,2,\dots ,m-1}$ sind die Repräsentanten der unterschiedlichen Restklassen. Ist${\displaystyle a}$ eine Primitivwurzel modulo${\displaystyle m}$, so nimmt der Ausdruck${\displaystyle a^t(\text{mod }m)}$ für${\displaystyle t\in \{0,1,2,\dots ,m-2\}}$ alle Werte aus${\displaystyle \{1,\dots ,m-1\}}$ (in scheinbar zufälliger Reihenfolge) an.

Die folgende Tabelle zeigt die Primitivwurzeln modulo der Primzahlen bis 100.

${\displaystyle m}$	${\displaystyle \phi (\phi (m))}$	Primitivwurzeln modulo${\displaystyle m}$
2	1	1
3	1	2
5	2	2, 3
7	2	3, 5
11	4	2, 6, 7, 8
13	4	2, 6, 7, 11
17	8	3, 5, 6, 7, 10, 11, 12, 14
19	6	2, 3, 10, 13, 14, 15
23	10	5, 7, 10, 11, 14, 15, 17, 19, 20, 21
29	12	2, 3, 8, 10, 11, 14, 15, 18, 19, 21, 26, 27
31	8	3, 11, 12, 13, 17, 21, 22, 24
37	12	2, 5, 13, 15, 17, 18, 19, 20, 22, 24, 32, 35
41	16	6, 7, 11, 12, 13, 15, 17, 19, 22, 24, 26, 28, 29, 30, 34, 35
43	12	3, 5, 12, 18, 19, 20, 26, 28, 29, 30, 33, 34
47	22	5, 10, 11, 13, 15, 19, 20, 22, 23, 26, 29, 30, 31, 33, 35, 38, 39, 40, 41, 43, 44, 45
53	24	2, 3, 5, 8, 12, 14, 18, 19, 20, 21, 22, 26, 27, 31, 32, 33, 34, 35, 39, 41, 45, 48, 50, 51
59	28	2, 6, 8, 10, 11, 13, 14, 18, 23, 24, 30, 31, 32, 33, 34, 37, 38, 39, 40, 42, 43, 44, 47, 50, 52, 54, 55, 56
61	16	2, 6, 7, 10, 17, 18, 26, 30, 31, 35, 43, 44, 51, 54, 55, 59
67	20	2, 7, 11, 12, 13, 18, 20, 28, 31, 32, 34, 41, 44, 46, 48, 50, 51, 57, 61, 63
71	24	7, 11, 13, 21, 22, 28, 31, 33, 35, 42, 44, 47, 52, 53, 55, 56, 59, 61, 62, 63, 65, 67, 68, 69
73	24	5, 11, 13, 14, 15, 20, 26, 28, 29, 31, 33, 34, 39, 40, 42, 44, 45, 47, 53, 58, 59, 60, 62, 68
79	24	3, 6, 7, 28, 29, 30, 34, 35, 37, 39, 43, 47, 48, 53, 54, 59, 60, 63, 66, 68, 70, 74, 75, 77
83	40	2, 5, 6, 8, 13, 14, 15, 18, 19, 20, 22, 24, 32, 34, 35, 39, 42, 43, 45, 46, 47, 50, 52, 53, 54, 55, 56, 57, 58, 60, 62, 66, 67, 71, 72, 73, 74, 76, 79, 80
89	40	3, 6, 7, 13, 14, 15, 19, 23, 24, 26, 27, 28, 29, 30, 31, 33, 35, 38, 41, 43, 46, 48, 51, 54, 56, 58, 59, 60, 61, 62, 63, 65, 66, 70, 74, 75, 76, 82, 83, 86
97	32	5, 7, 10, 13, 14, 15, 17, 21, 23, 26, 29, 37, 38, 39, 40, 41, 56, 57, 58, 59, 60, 68, 71, 74, 76, 80, 82, 83, 84, 87, 90, 92

Ist${\displaystyle p}$ eineungerade Primzahl, dann ist eine Primitivwurzel modulo${\displaystyle p^{\alpha }}$ mit${\displaystyle \alpha >1}$ auch Primitivwurzel modulo kleineren Potenzen von${\displaystyle p}$. Interessant für die Suche nach Primitivwurzeln modulo höheren Potenzen von${\displaystyle p}$ ist, dass eine Primitivwurzel${\displaystyle \gamma }$ modulo${\displaystyle p^2}$ (mit${\displaystyle 2\le \gamma \le p^2-1}$) auch Primitivwurzel zu allen höheren Potenzen von${\displaystyle p}$ ist.^[2]Daher genügt es für höhere Potenzen der Primzahl${\displaystyle p}$,

• eine Primitivwurzel${\displaystyle {\gamma }_1}$ modulo${\displaystyle p}$ zu finden (unter den Zahlen${\displaystyle 2,3,\dots ,p-1}$),

• die Zahlen${\displaystyle {\gamma }_1+k\cdot p,(0\le k\le p-1)}$ daraufhin zu testen, ob sie Primitivwurzeln modulo${\displaystyle p^2}$ sind. Notwendig und bereits hinreichend dafür ist, dass${\displaystyle ({\gamma }_1+k\cdot p{)}^{p-1}\not\equiv 1(\text{mod }{p}^2)}$ ist. Tatsächlich tritt dies bereits für${\displaystyle k=0}$ oder${\displaystyle k=1}$ ein, d. h.${\displaystyle {\gamma }_1}$ oder${\displaystyle {\gamma }_1+p}$ ist eine Primitivwurzel modulo${\displaystyle p^2}$.^[2]

Dann hat man mit jeder im zweiten Schritt bestimmten Zahl${\displaystyle {\gamma }_2}$ eine Primitivwurzel modulo${\displaystyle p^{\alpha }}$ für beliebige${\displaystyle \alpha \in \mathbb{N}}$.

Ist die so bestimmte Primitivwurzel${\displaystyle {\gamma }_2}$ ungerade, dann ist sie auch Primitivwurzel modulo${\displaystyle 2\cdot p^{\alpha }}$, sonst gilt dies für${\displaystyle {\gamma }_2+p^{\alpha }}$.

Primitivwurzeln finden eine Anwendung imDiffie-Hellman-Schlüsselaustausch, einem 1976 veröffentlichtenkryptografischen Verfahren zum öffentlichen Schlüsselaustausch. Dessen Sicherheit beruht auf der Tatsache, dass

• es einfach ist, zu einer gegebenen Primzahl${\displaystyle p}$, Primitivwurzel${\displaystyle g}$ und ganzen Zahl${\displaystyle a}$ ein${\displaystyle A}$ auszurechnen mit${\displaystyle A\equiv g^a(\text{mod }p)}$,

es aber

• aufwendig ist, für ein bekanntes${\displaystyle A}$ ein entsprechendes${\displaystyle a}$ (den sogenanntendiskreten Logarithmus) zu finden.

• Berechnung primitiver Wurzeln

DieDisquisitiones Arithmeticae wurden vonCarl Friedrich Gauß auf Lateinisch veröffentlicht. Die zeitgenössische deutsche Übersetzung umfasst alle seine Schriften zur Zahlentheorie:

• Carl Friedrich Gauß:Untersuchungen über höhere Arithmetik (deutsche Übersetzung), Original: Leipzig 1801.
• Peter Bundschuh:Einführung in die Zahlentheorie. 5. Auflage. Springer Verlag, 2002,ISBN 3-540-43579-4, S. 109–120
• Armin Leutbecher:Zahlentheorie – Eine Einführung in die Algebra. 1. Auflage. Springer Verlag, 1996, Berlin Heidelberg New York.ISBN 3-540-58791-8.

1. ↑Letztere liegt generell noch näher an der Elementordnung, denn es gilt für alle${\displaystyle a,m}$

   ${\displaystyle {\mathrm{ord}}_m(a)|\lambda (m)|\phi (m)}$.

2. ↑^abcA. Leutbecher:Zahlentheorie – Eine Einführung in die Algebra. S. 53–54.
3. ↑Carl Friedrich Gauss: Untersuchungen über höhere Arithmetik. H. Maser, 1889, S. Art. 92, abgerufen am 30. Januar 2017. 

• Zahlentheorie