kleiner Fermat Beweis mit Satz von Lagrange, Ende des Beweises unklar

01.01.2013, 23:44

Very

kleiner Fermat Beweis mit Satz von Lagrange, Ende des Beweises unklar

Hallo,
ich bin mittlerweile bei einem weiteren Beweis in meinem Skript zum kleinen Fermat angekommen, welcher über die Gruppentheorie geht. Und dabei ist mir der Schluss nicht ganz klar, bzw. mir ist nicht klar, warum wir da schon fertig sind wo wir fertig sind.

zum Beweis
Wir wissen bereits dass $\begin{eqnarray*} \mathbb{Z}/p\mathbb{Z} \end{eqnarray*}$ Körper ist, wenn p prim. Damit ist insbesondere $\begin{eqnarray*} (G=\mathbb{Z}/p\mathbb{Z} \end{eqnarray*}$ \ $\begin{eqnarray*} \{0\}, \cdot ) \end{eqnarray*}$ eine Gruppe.
Es gilt |G|=p-1, da G genau p-1 Elemente besitzt.

$\begin{eqnarray*} H=\{a,a^2, \ldots, a^{ord(a)}\} \end{eqnarray*}$ ist eine Teilmenge der Gruppe G und da abgeschlossen auch eine Untergruppe von G.

Es gilt |H|=ord(a)

Damit folgt nach dem Satz von Lagrange (Ordnung der Untergruppe teilt die Ordnung der Gruppe), dass ord(a)|(p-1).

Damit endet der Beweis im Skript.

Ich möchte aber doch zeigen, dass $\begin{eqnarray*} a^{p-1}=1 (mod p) \end{eqnarray*}$ und sehe noch nicht, wie ich darauf komme...

Verwende ich die Definition für Kongruenz, könnte ich ord(a)|(p-1) noch umschreiben zu

$\begin{eqnarray*} p \equiv 1 (mod \text{ }ord(a)) \end{eqnarray*}$ , das liefert aber noch nicht das Gewünschte..

Würde mich über Hilfe sehr freuen.
lg Very

01.01.2013, 23:50

watcher

Auf diesen Beitrag antworten »

Hallo,

was ist die Definition der Ordnung eines Elements bei euch?

01.01.2013, 23:55

Very

Auf diesen Beitrag antworten »

Definition der Ordnung:

Sei $\begin{eqnarray*} x \in \mathbb{Z}/n\mathbb{Z} \end{eqnarray*}$ . mit ggT(x,n)=1.
Dann existiert ein minimales $\begin{eqnarray*} k \in \mathbb{Z} \end{eqnarray*}$ mit $\begin{eqnarray*} x^k \equiv 1\text{ } (mod n) \end{eqnarray*}$ . Wir nennen ord(x):=k die multiplikative Ordnung von x.

02.01.2013, 00:01

watcher

Auf diesen Beitrag antworten »

So und nach Lagrange ist $\begin{eqnarray*} p-1 = ord(a) \cdot \text{irgendwas} \end{eqnarray*}$

Und wir wissen ja was $\begin{eqnarray*} x^{ord(a)} \end{eqnarray*}$ ist nach Definition.

02.01.2013, 00:17

Very

Auf diesen Beitrag antworten »

$\begin{eqnarray*} x^{ord(a)}=1 \end{eqnarray*}$

Wenn ich jetzt jeweils a hoch deine Gleichung nehme erhalte ich (mit irgendwas =c)

$\begin{eqnarray*} a^{p-1}=a^{{ord(a)}^c} \end{eqnarray*}$
$\begin{eqnarray*} a^{p-1}= 1 \end{eqnarray*}$ da 1 hoch irgendwas immer =1

Mein Ziel ist ja $\begin{eqnarray*} a^{p} \equiv a (mod p) \end{eqnarray*}$

Jetzt fehlt mir noch das modulo p... denn wenn ich das hätte, würde es voll durchlaufen und zwar.

$\begin{eqnarray*} a^{p-1} \equiv 1 (mod p) \end{eqnarray*}$

Wenn ggT(p,a)=1 (ist es das denn immer? - ich meine a könnte ja auch gleich p sein und dann wäre der ggT(p,p) = p)
darf ich "kürzen" und erhalte:

$\begin{eqnarray*} a^p \equiv a (mod p) \end{eqnarray*}$

Das müsste jetzt bis auf die Lücken richtig sein, oder?

02.01.2013, 00:23

watcher

Auf diesen Beitrag antworten »

Zitat:

Deine ersten drei Gleichcheiten sind natürlich Gleichheiten modulo p.
Wo sollte das denn auch sonst gelten.

02.01.2013, 00:36

Very

Auf diesen Beitrag antworten »

Zitat:

$\begin{eqnarray*} x^{ord(a)} \equiv 1 \end{eqnarray*}$ Wenn ich jetzt jeweils a hoch deine Gleichung nehme erhalte ich (mit irgendwas =c) $\begin{eqnarray*} a^{p-1}=a^{{ord(a)}^c} \end{eqnarray*}$ also $\begin{eqnarray*} a^{p-1} \equiv 1 \end{eqnarray*}$ da 1 hoch irgendwas immer =1

ok, die erste Äquivalenz kommt wegen der Ordnung rein und die dritte gilt, weil ich da die Ordnung eingesetzt habe. Die zweite ist mir noch nicht ganz klar:

Kommt die weil ich oben schon $\begin{eqnarray*} \mathbb{Z}/p \mathbb{Z} \end{eqnarray*}$ betrachte?

Aber eigentlich müsste es auch ohne diese gehen... denn ich habe ja dann insgesamt:
$\begin{eqnarray*} a^{p-1} \equiv 1 (mod p) \end{eqnarray*}$

Noch unklar ist mir warum ggT(a,p)= 1 ist.
Ich hatte doch für a gar keine Einschränkungen gemacht - a könnte alles sein, auch p und damit wäre der ggT(a,p)=p... Warum kann ich das denn ausschließen um den letzten Schritt zu gehen?

02.01.2013, 00:45

watcher

Auf diesen Beitrag antworten »

Du bist die \color{red}ganze\color{red} Zeit in der Gruppe (\mathbb Z/ p\mathbb Z^*, \cdot ) musst also auch beachten wann zwei Elemente darin gleich sind.
Und das geht nunmal über modulo Rechnung.
Auch das mit dem ggT ist damit ziemlich banal.
Ist ggT(a,p)=1 so ist $\begin{eqnarray*} a\not \equiv 0 \mod p \end{eqnarray*}$ und die vorige Rechnung greift und für ggT(a,p)=1 gilt $\begin{eqnarray*} a^p \equiv a \mod p \end{eqnarray*}$ banalerweise.

02.01.2013, 00:58

Very

Auf diesen Beitrag antworten »

ah, ok... ich glaub jetzt hab ichs verstanden... wir sind sowieso die ganze Zeit in der Gruppe und rechnen daher nur modulo...

Zitat:

Ist ggT(a,p)=1 so ist $\begin{eqnarray*} a\not \equiv 0 \mod p \end{eqnarray*}$ und die vorige Rechnung greift und für ggT(a,p)=1 gilt $\begin{eqnarray*} a^p \equiv a \mod p \end{eqnarray*}$ banalerweise.

Der erste Fall gilt für alle a mit ggT(a,p)=1
und der zweite Fall für a=p (Du meintest hinten für ggT(a,p)=p, oder?)
Und etwas anderes kann nicht vorkommen. Also passt alles.

Vielen Dank für deine Hilfe und Geduld smile

Neue Frage »

Antworten »

kleiner Fermat Beweis mit Satz von Lagrange, Ende des Beweises unklar

Verwandte Themen