Umformungsschritt im Beweis < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Beweis des kleinen Fermat´schen Satzes.
Wenn p eine Primzahl ist, dann gilt [mm] x^{p} [/mm] = x mod p für jede ganze Zahl x.
Beweise den Satz für ganze Zahlen. |
Hallo,
ich beschäftige mich mit einem Mathebuch, indem der kleine Fermat´sche Satz bewiesen wird.
Im großen und ganzen verstehe ich den Induktionsbeweis, lediglich ein Schritt ist mir nicht klar und ich hoffe mir kann jemand erklären, wie dieser zustande kommt.
Hier der Induktionsbeweises :
[mm] (x+1)^{p} [/mm] = [mm] x^{p} [/mm] + [mm] \pmat{ p \\ 1 }x^{p-1} [/mm] + [mm] \pmat{ p \\ 2 } x^{p-2} [/mm] + ... + [mm] \pmat{ p \\ p - 1 }x+1
[/mm]
Man rechnet modulo p
[mm] (x+1)^{p} [/mm] = [mm] x^{p} [/mm] + [mm] \pmat{ p \\ 1 }x^{p-1} [/mm] + [mm] \pmat{ p \\ 2 } x^{p-2} [/mm] + ... + [mm] \pmat{ p \\ p - 1 }x+1 [/mm] mod p
So und nun kommt der Schritt, den ich nicht nachvollziehen kann (irgendwie verschwindet der Exponent p im ersten x rechts des Gleichheitszeichens) :
= x + [mm] \pmat{ p \\ 1 }x^{p-1} [/mm] + [mm] \pmat{ p \\ 2 } x^{p-2} [/mm] + ... + [mm] \pmat{ p \\ p - 1 }x+1 [/mm] mod p
Die darauf folgenden Schritte sind dann wieder kein Problem.
Beim zweiten Teil ( dem Beweis für ganze Zahlen x) bin ich mir nicht so sicher; ich würde es mal so verfassen:
Ich setze x < 0 voraus; wenn wir x´= - x setzen, dann muss x´als das Negative eines Negativen positiv sein. Weshalb der Beweis für ganze Zahlen verwwendet werden kann.
Ich habe keine Ahnung ob dies als Beweis in Ordnung ist, aber auf einen anderen Weg komme ich einfach nicht.
Eine weitere Frage kommt mir dabei in den Kopf :
Manchmal wird der kleine Fermatsch´e Satz auch wie folgt dargestellt :
Wenn p eine Primzahl ist, die die Ganze Zahl x nicht teilt, dann gilt [mm] x^{p-1} [/mm] = 1 mod p.
Ich frage mich, ob die erste Variante nicht stärker ist, da p hier nicht die Einschränkung erfährt kein Teiler von x zu sein?
Da ich den Beweis gerne durchblicken würde bin ich für jede Hilfe dankbar.
Liebe Grüße
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 08:24 Mo 06.06.2016 | | Autor: | hippias |
> Beweis des kleinen Fermat´schen Satzes.
> Wenn p eine Primzahl ist, dann gilt [mm]x^{p}[/mm] = x mod p für
> jede ganze Zahl x.
>
> Beweise den Satz für ganze Zahlen.
> Hallo,
>
> ich beschäftige mich mit einem Mathebuch, indem der kleine
> Fermat´sche Satz bewiesen wird.
>
> Im großen und ganzen verstehe ich den Induktionsbeweis,
> lediglich ein Schritt ist mir nicht klar und ich hoffe mir
> kann jemand erklären, wie dieser zustande kommt.
>
> Hier der Induktionsbeweises :
>
> [mm](x+1)^{p}[/mm] = [mm]x^{p}[/mm] + [mm]\pmat{ p \\ 1 }x^{p-1}[/mm] + [mm]\pmat{ p \\ 2 } x^{p-2}[/mm]
> + ... + [mm]\pmat{ p \\ p - 1 }x+1[/mm]
>
> Man rechnet modulo p
>
> [mm](x+1)^{p}[/mm] = [mm]x^{p}[/mm] + [mm]\pmat{ p \\ 1 }x^{p-1}[/mm] + [mm]\pmat{ p \\ 2 } x^{p-2}[/mm]
> + ... + [mm]\pmat{ p \\ p - 1 }x+1[/mm] mod p
>
> So und nun kommt der Schritt, den ich nicht nachvollziehen
> kann (irgendwie verschwindet der Exponent p im ersten x
> rechts des Gleichheitszeichens) :
>
> = x + [mm]\pmat{ p \\ 1 }x^{p-1}[/mm] + [mm]\pmat{ p \\ 2 } x^{p-2}[/mm] +
> ... + [mm]\pmat{ p \\ p - 1 }x+1[/mm] mod p
Hier dürfte die Induktionsvoraussetzung [mm] $x^{p}= x\mod [/mm] p$ angwendet worden sein.
>
> Die darauf folgenden Schritte sind dann wieder kein
> Problem.
>
>
>
>
> Beim zweiten Teil ( dem Beweis für ganze Zahlen x) bin ich
> mir nicht so sicher; ich würde es mal so verfassen:
>
> Ich setze x < 0 voraus; wenn wir x´= - x setzen, dann muss
> x´als das Negative eines Negativen positiv sein. Weshalb
> der Beweis für ganze Zahlen verwwendet werden kann.
Wenn die Behauptung für nicht negative $x$ gilt, dann gilt für $x<0$, dass [mm] $(-x)^{p}= -x\mod [/mm] p$. Löse die Klamer auf; beachte den Fall $p=2$ gesondert.
>
> Ich habe keine Ahnung ob dies als Beweis in Ordnung ist,
> aber auf einen anderen Weg komme ich einfach nicht.
>
>
>
> Eine weitere Frage kommt mir dabei in den Kopf :
> Manchmal wird der kleine Fermatsch´e Satz auch wie folgt
> dargestellt :
>
> Wenn p eine Primzahl ist, die die Ganze Zahl x nicht teilt,
> dann gilt [mm]x^{p-1}[/mm] = 1 mod p.
>
> Ich frage mich, ob die erste Variante nicht stärker ist,
> da p hier nicht die Einschränkung erfährt kein Teiler von
> x zu sein?
Die beiden Formulierungen sind äquivalent. Übrigens: wenn [mm] $p\vert [/mm] x$, dann ist $x= [mm] 0\mod [/mm] p$ und [mm] $x^{p}= 0\mod [/mm] p$.
>
> Da ich den Beweis gerne durchblicken würde bin ich für
> jede Hilfe dankbar.
>
> Liebe Grüße
>
|
|
|
| |
|
| Aufgabe | | Wenn die Behauptung für nicht negative x gilt, dann gilt für x<0, dass $ [mm] (-x)^{p}= -x\mod [/mm] p $. Löse die Klamer auf; beachte den Fall p=2 gesondert. |
Erstmal vielen Dank für deine Hilfe.
Da ich keinerlei vorerfahrung in modularer Arithmetik habe vordern mich die Übungsaufgaben hierzu wirklich heraus, daher nochmal Danke.
Zu der Angabe "Wenn die Behauptung für nicht negative x gilt, dann gilt für x<0, dass $ [mm] (-x)^{p}= -x\mod [/mm] p $. Löse die Klamer auf; beachte den Fall p=2 gesondert. " habe ich noch eine Frage.
Ich würde die Sache so angehen :
P=2:
[mm] (-(-x))^2 [/mm] = -(-x) mod p
[mm] x^2 [/mm] = x mod p.
und für P [mm] \not= [/mm] 2
[mm] (-(-x))^2 [/mm] = -(-x) mod p
[mm] x^2 [/mm] = x mod p.
Sehe ich die Situation nun richtig, oder habe ich mich total verrant?
Liebe Grüße
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:40 Mi 08.06.2016 | | Autor: | hippias |
Das ist nicht das, was ich vorhatte: Du hast ja doppelt negiert.
Die Situation ist, dass für [mm] $x\in \IZ$ [/mm] mit [mm] $x\geq [/mm] 0$ die Kongruenz [mm] $x^{p}= x\mod [/mm] p$ bewiesen ist.
Nun willst Du beweisen, dass diese Kongruenz auch für negative $x$ gilt.
Dazu sei [mm] $x\in \IZ$ [/mm] negativ. Dann ist $-x$ ganze Zahl und positiv, d.h. nach dem bereits bewiesenen gilt [mm] $(-x)^{p}= [/mm] -x [mm] \mod [/mm] p$.
Im Fall $p=2$ gilt für alle [mm] $y\in \IZ$, [/mm] dass $-y= [mm] y\mod [/mm] p$. Daher kann jedes $-x$ oben durch $x$ ersetzt werden: [mm] $x^{p}= [/mm] x [mm] \mod [/mm] p$.
Im Fall $p>2$ ist $p$ ungerade, sodass man sagen kann, dass [mm] $(-x)^{p}= (-1)^{p}x^{p}= -(x^{p})$ [/mm] gilt. Dies liefert die Kongruenzen [mm] $-(x^{p})= (-x)^{p}= -x\mod [/mm] p$, sodass [mm] $x^{p}= x\mod [/mm] p$ folgt.
Also gilt die Kongruenz für alle Primzahlen und alle [mm] $x\in \IZ$.
[/mm]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:03 Do 09.06.2016 | | Autor: | Windbeutel |
Jetzt verstehe ich.
Vielen Dank für deine Mühe.
|
|
|
|
