matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenUni-Analysis-InduktionUmformungsschritt im Beweis
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Deutsch • Englisch • Französisch • Latein • Spanisch • Russisch • Griechisch
Forum "Uni-Analysis-Induktion" - Umformungsschritt im Beweis
Umformungsschritt im Beweis < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Uni-Analysis-Induktion"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Umformungsschritt im Beweis: Erklärung
Status: (Frage) beantwortet Status 
Datum: 07:37 Mo 06.06.2016
Autor: Windbeutel

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


        
Bezug
Umformungsschritt im Beweis: Antwort
Status: (Antwort) fertig Status 
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
>  


Bezug
                
Bezug
Umformungsschritt im Beweis: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 10:27 Mi 08.06.2016
Autor: Windbeutel

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


Bezug
                        
Bezug
Umformungsschritt im Beweis: Antwort
Status: (Antwort) fertig Status 
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]



Bezug
                                
Bezug
Umformungsschritt im Beweis: Danke
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 09:03 Do 09.06.2016
Autor: Windbeutel

Jetzt verstehe ich.
Vielen Dank für deine Mühe.

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Uni-Analysis-Induktion"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]