Primitivwurzeln

28.10.2008, 14:23

Bjoern1982

Primitivwurzeln

Hallo,

Sei p prim und a aus Z mit p teilerfremd zu a
zu zeigen ist die folgende Äquivalenz:

a ist Primitivwurzel modulo p <=> Es gilt $\begin{eqnarray*} a^\frac{p-1}{q} \not\equiv 1\ mod\ p \end{eqnarray*}$ für alle Primteiler q von p-1

Ok, fangen wir dann erstmal mit der einen Richtung an

=>

a ist Primitivwurzel mod p

Das heisst es gilt $\begin{eqnarray*} ord_p(a)=n=\varphi(p)=p-1 \end{eqnarray*}$ wobei n die kleinste natürliche Zahl ist, die $\begin{eqnarray*} a^n\equiv 1\ mod\ p \end{eqnarray*}$ erfüllt, woraus ja direkt der kleine Fermat $\begin{eqnarray*} a^{p-1} \equiv 1\ mod\ p \end{eqnarray*}$ folgt.

Wie geht es nun weiter ?

28.10.2008, 15:18

system-agent

Auf diesen Beitrag antworten »

Überlege dir was die Ordnung von $\begin{eqnarray*} a \end{eqnarray*}$ ist.

So wie ich das sehe könntest du beim ersten Argument schon überall Äquivalenzen schreiben.

29.10.2008, 01:12

Bjoern1982

Auf diesen Beitrag antworten »

Oh ja

Die Ordnung ist p-1 und damit als untere Schranke die kleinste natürliche Zahl n, für die $\begin{eqnarray*} a^n\equiv 1\ mod\ p \end{eqnarray*}$ gilt, wodurch alle Zahlen die kleiner als p-1 sind, also auch (p-1)/q, nicht mehr kongruent 1 modulo p sein können Freude

Das wäre dann die eine Richtung oder ?

Und nun noch die andere:

<=

Es gilt $\begin{eqnarray*} a^\frac{p-1}{q} \not\equiv 1\ mod\ p \end{eqnarray*}$ für alle Primteiler q von p-1

Wie folgere ich daraus denn dass a eine Primitivwurzel modulo p ist verwirrt

Womöglich durch einen indirekten Beweis ?

Angenommen es würde folgen dass a keine Primitivwurzel mod p ist, dann wäre die Ordnung n auf jeden Fall schonmal kleiner als p-1. Nach dem Satz von Lagrange teilt n die Gruppenordung p-1, also gilt $\begin{eqnarray*} k \cdot n=p-1 <=> \frac{k \cdot n}{q}=\frac{p-1}{q}<=>(a^n)^{\frac{k}{q}}=a^{\frac{p-1}{q}} \end{eqnarray*}$

Wegen $\begin{eqnarray*} a^n\equiv 1\ mod\ p \end{eqnarray*}$ würde dann $\begin{eqnarray*} a^{\frac{p-1}{q}} \equiv 1\ mod\ p \end{eqnarray*}$ folgen, was ein Widerspruch wäre und somit das Gegenteil gelten muss, nämlich dass aus der Inkongruenz folgt dass a sehr wohl eine Primitivwurzel modulo p ist.

Ist das so in Ordnung ?

Edit:

Unabhängig von der Argumentation mit der Ordnung könnte man vielleicht auch ganz einfach so argumentieren ?

Wenn a Primitivwurzel modulo p ist, dann werden ja durch die Potenzen $\begin{eqnarray*} a^i \end{eqnarray*}$ alle Elemente einer zyklischen Gruppe $\begin{eqnarray*} {Z_p}^* \end{eqnarray*}$ erzeugt, wodurch ja dann automatsich nur $\begin{eqnarray*} a^0 \end{eqnarray*}$ kongruent zu 1 modulo p sein sollte und für alle anderen Exponenten i andere Reste entstehen müssen.
Wäre eine solche verbale Begründung auch denkbar ?

29.10.2008, 15:42

Auf diesen Beitrag antworten »

Zitat:

Original von Bjoern1982
Nach dem Satz von Lagrange teilt n die Gruppenordung p-1, also gilt $\begin{eqnarray*} k \cdot n=p-1 <=> \frac{k \cdot n}{q}=\frac{p-1}{q}<=>(a^n)^{\frac{k}{q}}=a^{\frac{p-1}{q}} \end{eqnarray*}$

Wegen $\begin{eqnarray*} a^n\equiv 1\ mod\ p \end{eqnarray*}$ würde dann $\begin{eqnarray*} a^{\frac{p-1}{q}} \equiv 1\ mod\ p \end{eqnarray*}$ folgen, was ein Widerspruch wäre und somit das Gegenteil gelten muss, nämlich dass aus der Inkongruenz folgt dass a sehr wohl eine Primitivwurzel modulo p ist.

Ist das so in Ordnung ?

Fast, es fehlt aber ein kleines entscheidendes Argument: Die Argumentation klappt so nur für Primzahlen $\begin{eqnarray*} q \end{eqnarray*}$ , die Teiler sind von $\begin{eqnarray*} k \end{eqnarray*}$ . Also solltest du wenigstens dazusagen, dass du für $\begin{eqnarray*} q \end{eqnarray*}$ irgendeinen Primteiler von $\begin{eqnarray*} k \end{eqnarray*}$ wählst, den es wegen $\begin{eqnarray*} k>1 \end{eqnarray*}$ ja geben muss.

29.10.2008, 16:18

Bjoern1982

Auf diesen Beitrag antworten »

Alles klar, vielen Dank smile

Neue Frage »

Antworten »

Primitivwurzeln

Verwandte Themen