Primitivwurzeln

18.06.2005, 15:22	Holdgrün	Auf diesen Beitrag antworten »
Primitivwurzeln Hallo Leute, wir beschäftigen uns in der Zahlentheorie gerade mit Primitivwurzeln. Was sind eigentlich Primitivwurzeln? OK und dann wissen wir, dass 3 eine Primitivwurzel modulo 31 ist. Wie kommt man darauf und wie findet man die restlichen Primitivwurzeln modulo 31? Vielen Dank!
18.06.2005, 15:41	AD	Auf diesen Beitrag antworten »
Laut Satz von Fermat-Euler gilt für alle zum Modul $\begin{eqnarray} m \end{eqnarray}$ teilerfremden $\begin{eqnarray} a \end{eqnarray}$ die Gleichung $\begin{eqnarray} a^{\varphi(m)}\equiv 1\mod m \end{eqnarray}$ D.h., für jede solche Zahl a kann man auch nach dem kleinsten Nenner $\begin{eqnarray} d>1 \end{eqnarray}$ mit der Eigenschaft $\begin{eqnarray} a^d\equiv 1\mod m \end{eqnarray}$ fragen. Auf alle Fälle ist dieses $\begin{eqnarray} d \end{eqnarray}$ ein Teiler von $\begin{eqnarray} \varphi(m) \end{eqnarray}$ . Gilt nun direkt $\begin{eqnarray} d=\varphi(m) \end{eqnarray}$ , so bezeichnet man das zugehörige $\begin{eqnarray} a \end{eqnarray}$ als primitive Wurzel modulo $\begin{eqnarray} m \end{eqnarray}$ . Das besondere daran ist, dass dann die Restklassen $\begin{eqnarray} a^0,a^1,\ldots,a^{\varphi(m)-1} \end{eqnarray}$ sämtlich verschieden sind und damit die gesamte primen Restklassen modulo $\begin{eqnarray} m \end{eqnarray}$ darstellen. Bei der Frage der Überprüfung, ob eine gegebene Zahl $\begin{eqnarray} a \end{eqnarray}$ primitive Wurzel modulo $\begin{eqnarray} m \end{eqnarray}$ ist, bin ich nicht mehr ganz sattelfest: Auf alle Fälle genügt es, wenn $\begin{eqnarray} a \end{eqnarray}$ teilerfremd zu $\begin{eqnarray} m \end{eqnarray}$ ist und zudem für alle Primteiler $\begin{eqnarray} p \end{eqnarray}$ von $\begin{eqnarray} \varphi(m) \end{eqnarray}$ die Ungleichung $\begin{eqnarray} a^{\frac{\varphi(m)}{p}}\not\equiv 1\mod m \end{eqnarray}$ erfüllt ist. Möglicherweise gibt es aber auch ein einfacheres Kriterium (Zahlentheorieexperten, bitte melden!). Gibt es auch nur eine primitive Wurzel $\begin{eqnarray} a \end{eqnarray}$ , dann kriegt man alle $\begin{eqnarray} \varphi(\varphi(m)) \end{eqnarray}$ primitiven Wurzeln einfach durch die Potenzen $\begin{eqnarray} a^t \end{eqnarray}$ , wobei $\begin{eqnarray} t \end{eqnarray}$ die primen Restklassen modulo $\begin{eqnarray} \varphi(m) \end{eqnarray}$ durchläuft.
18.06.2005, 15:53	Leopold	Auf diesen Beitrag antworten »
Und im Beispiel wären das (alle Rechnungen modulo 31) $\begin{eqnarray} 3^1 = 3 \, , \ 3^7 = 17 \, , \ 3^{11} = 13 \, , \ 3^{13} = 24 \, , \ 3^{17} = 28 \, , \ 3^{19} = 4 \, , \ 3^{23} = 14 \, , \ 3^{29} = 7 \end{eqnarray}$ Die Exponenten sind gerade die zu $\begin{eqnarray} 30 = \varphi{(31)} \end{eqnarray}$ teilerfremden Zahlen unterhalb $\begin{eqnarray} 30 \end{eqnarray}$ .

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »