www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Vorhilfe
  Status Geisteswiss.
    Status Erdkunde
    Status Geschichte
    Status Jura
    Status Musik/Kunst
    Status Pädagogik
    Status Philosophie
    Status Politik/Wirtschaft
    Status Psychologie
    Status Religion
    Status Sozialwissenschaften
  Status Informatik
    Status Schule
    Status Hochschule
    Status Info-Training
    Status Wettbewerbe
    Status Praxis
    Status Internes IR
  Status Ingenieurwiss.
    Status Bauingenieurwesen
    Status Elektrotechnik
    Status Maschinenbau
    Status Materialwissenschaft
    Status Regelungstechnik
    Status Signaltheorie
    Status Sonstiges
    Status Technik
  Status Mathe
    Status Schulmathe
    Status Hochschulmathe
    Status Mathe-Vorkurse
    Status Mathe-Software
  Status Naturwiss.
    Status Astronomie
    Status Biologie
    Status Chemie
    Status Geowissenschaften
    Status Medizin
    Status Physik
    Status Sport
  Status Sonstiges / Diverses
  Status Sprachen
    Status Deutsch
    Status Englisch
    Status Französisch
    Status Griechisch
    Status Latein
    Status Russisch
    Status Spanisch
    Status Vorkurse
    Status Sonstiges (Sprachen)
  Status Neuerdings
  Status Internes VH
    Status Café VH
    Status Verbesserungen
    Status Benutzerbetreuung
    Status Plenum
    Status Datenbank-Forum
    Status Test-Forum
    Status Fragwürdige Inhalte
    Status VH e.V.

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:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Zahlentheorie" - Beweise
Beweise < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Zahlentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Beweise: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 21:51 Mi 31.10.2012
Autor: MattiJo

Aufgabe
(a) Ist p eine Primzahl p > 5, so gilt [mm] 240|(p^4 [/mm] − 1).

(b) Zeige mittels der beiden Beziehungen 827 = 67m + y und 559 = 67n + y mit m,n,y ∈ N die
Aussage 67| [mm] (827^n [/mm] − [mm] 559^n) [/mm] für alle n ∈ N.

(c) Zeige 360 | [mm] n^2 \cdot (n^2 [/mm] − 1) [mm] \cdot (n^2 [/mm] − 4)für alle n ∈ N.



Hallo allerseits,

ich versuche gerade obige Aufgaben zu lösen. Da es sich mal wieder um Beweise handelt, habe ich mal wieder Probleme ;-)

Beginnend mit der (a): Meine Idee war es zunächst einmal, den Term in Faktoren zu zerlegen: [mm] p^4 [/mm] - 1 = [mm] (p^2 [/mm] + 1)(p-1)(p+1)

Jetzt würde ich jeden einzelnen Term gerne auf Teilbarkeit durch 240 testen - aber wie kann ich denn dazu "die Menge der Primzahlen" in Betracht ziehen, damit der Beweis für alle Primzahlen gültig ist?

        
Bezug
Beweise: Antwort
Status: (Antwort) fertig Status 
Datum: 22:03 Mi 31.10.2012
Autor: abakus


> (a) Ist p eine Primzahl p > 5, so gilt [mm]240|(p^4[/mm] − 1).
>  
> (b) Zeige mittels der beiden Beziehungen 827 = 67m + y und
> 559 = 67n + y mit m,n,y ∈ N die
>  Aussage 67| [mm](827^n[/mm] − [mm]559^n)[/mm] für alle n ∈ N.
>
> (c) Zeige 360 | [mm]n^2 \cdot (n^2[/mm] − 1) [mm]\cdot (n^2[/mm] − 4)für
> alle n ∈ N.
>  
>
> Hallo allerseits,
>  
> ich versuche gerade obige Aufgaben zu lösen. Da es sich
> mal wieder um Beweise handelt, habe ich mal wieder Probleme
> ;-)
>  
> Beginnend mit der (a): Meine Idee war es zunächst einmal,
> den Term in Faktoren zu zerlegen: [mm]p^4[/mm] - 1 = [mm](p^2[/mm] +
> 1)(p-1)(p+1)
>  
> Jetzt würde ich jeden einzelnen Term gerne auf Teilbarkeit
> durch 240 testen

... was konkret bedeutet: Teilbarkeit durch 3, durch 5 und durch 16.
3 ist einfach: p-1, p und p+1 sind drei aufeinander folgende Zahlen, und p ist als Primzahl meist nicht durch 3 teilbar. Ergo?
Zur Teilbarkeit durch 5 kannst du auf [mm] $p^4-1$ [/mm] direkt mit dem kleinen Fermat draufhauen.
Die drei Faktoren deiner Zerlegung sind alle gerade Zahlen, vielleicht ist sogar eine durch 4 teilbare dabei...
Gruß Abakus

> - aber wie kann ich denn dazu "die Menge
> der Primzahlen" in Betracht ziehen, damit der Beweis für
> alle Primzahlen gültig ist?


Bezug
                
Bezug
Beweise: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 22:34 Mi 31.10.2012
Autor: MattiJo

>... was konkret bedeutet: Teilbarkeit durch 3, durch 5 und durch 16.
>3 ist einfach: p-1, p und p+1 sind drei aufeinander folgende Zahlen, und p ist als Primzahl meist nicht durch 3 teilbar. Ergo?

...damit müsste doch entweder p-1 ODER p+1 auf jeden Fall durch 3 teilbar sein...
Wie kann ich das mathematisch als Beweis formulieren?

p-1,p,p+1 bildet eine Reihe ganzer Zahlen, folglich gilt
3|p-1  ˅  3|p+1

Geht das so?

>Zur Teilbarkeit durch 5 kannst du auf [mm] p^4 [/mm] - 1 direkt mit dem kleinen Fermat draufhauen.
>Die drei Faktoren deiner Zerlegung sind alle gerade Zahlen, vielleicht ist sogar eine durch 4 teilbare dabei...

Wie mache ich das mit dem kleinen Fermat? Den Satz habe ich nicht wirklich verstanden in der Vorlesung...
Es ist [mm] a^{p-1} [/mm] ≡ 1 mod p . Bedeutet das, dass p | [mm] a^{p-1} [/mm] - 1 ?
Wie kann ich das dann auf [mm] p^4-1 [/mm] anwenden?


Bezug
                        
Bezug
Beweise: Antwort
Status: (Antwort) fertig Status 
Datum: 23:40 Mi 31.10.2012
Autor: abakus


> >... was konkret bedeutet: Teilbarkeit durch 3, durch 5 und
> durch 16.
> >3 ist einfach: p-1, p und p+1 sind drei aufeinander
> folgende Zahlen, und p ist als Primzahl meist nicht durch 3
> teilbar. Ergo?
>
> ...damit müsste doch entweder p-1 ODER p+1 auf jeden Fall
> durch 3 teilbar sein...
>  Wie kann ich das mathematisch als Beweis formulieren?
>  
> p-1,p,p+1 bildet eine Reihe ganzer Zahlen, folglich gilt
> 3|p-1  ˅  3|p+1
>  
> Geht das so?
>  
> >Zur Teilbarkeit durch 5 kannst du auf [mm]p^4[/mm] - 1 direkt mit
> dem kleinen Fermat draufhauen.
> >Die drei Faktoren deiner Zerlegung sind alle gerade
> Zahlen, vielleicht ist sogar eine durch 4 teilbare dabei...
>
> Wie mache ich das mit dem kleinen Fermat? Den Satz habe ich
> nicht wirklich verstanden in der Vorlesung...
>  Es ist [mm]a^{p-1}[/mm] ≡ 1 mod p . Bedeutet das, dass p |
> [mm]a^{p-1}[/mm] - 1 ?

Da 5 eine Primzahl ist, gilt (falls eine Zahl a teilerfremd zu 5 ist)
[mm] $a^{5-1}\equiv [/mm] 1 mod 5$.
Nun ist meine Zahl a konkret eine Primzahl p, und alle Primzahlen (mit einer Ausnahme) sind teilerfremd zu 5.
Dan gilt [mm] $p^4\equiv [/mm] 1 mod 5$ und [mm] $p^4-1 \equiv [/mm] 0 mod 5$.

>  Wie kann ich das dann auf [mm]p^4-1[/mm] anwenden?
>  


Bezug
                                
Bezug
Beweise: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 00:44 Do 01.11.2012
Autor: MattiJo

Wenn ich es richtig verstehe, folgt dann aus $ [mm] p^4-1 \equiv [/mm] 0 mod 5 $ dann 5 | [mm] p^4-1 [/mm] bzw. ist vielleicht sogar eine äquivalente Schreibweise dafür...??
Reicht das dann als Beweis dafür, dass die 5 [mm] p^4-1 [/mm] teilt?

Heißt das, dass die Modulo-Operation hier eigentlich die Modulo-Umkehrfunktion ist? Ich kannte Modulo bislang eigentlich immer als Funktion, die zwei Parameter als Input hatte, diese aufgenommen hat und den Rest geliefert hat. Hier ist der Rest aber offensichtlich Input (0) , 5 der Teiler als 2. Input und als Output kommt die ursprüngliche Zahl heraus....oder sehe ich das falsch?

War meine Begründung von oben für die 3 eigentlich adäquat?
Dann brauche ich noch einen Beweis für die 16. Da hilft mir das vorherige Vorgehen offensichtlich nicht mehr weiter. Gibt es da einen weiteren Ansatz?

EDIT: habe im Internet gefunden, dass 8 | [mm] p^2 [/mm] - 1 für p prim (leider ohne Beweis). Ob das weiterhilft? Letztlich brauche ich ja 16= 2 [mm] \cdot [/mm] 8 als Teiler.


Bezug
                                        
Bezug
Beweise: Antwort
Status: (Antwort) fertig Status 
Datum: 00:49 Do 01.11.2012
Autor: reverend

Hallo MattiJo,

> Wenn ich es richtig verstehe, folgt dann aus [mm]p^4-1 \equiv 0 mod 5[/mm]
> dann 5 | [mm]p^4-1[/mm] bzw. ist vielleicht sogar eine äquivalente
> Schreibweise dafür...??

Ja, das ist äquivalent.

>  Reicht das dann als Beweis dafür, dass die 5 [mm]p^4-1[/mm]
> teilt?

Ja, das reicht für alle [mm] p\not=5. [/mm]
Mit dem "kleinen Fermat" musst Du Dich unbedingt auseinandersetzen, den brauchst Du immer wieder. Du musst den Satz verstehen, anwenden können und am besten auch seinen Beweis jederzeit reproduzieren können. Das ist absolut zentrales Wissen in der Zahlentheorie.

> Heißt das, dass die Modulo-Operation hier eigentlich die
> Modulo-Umkehrfunktion ist? Ich kannte Modulo bislang
> eigentlich immer als Funktion, die zwei Parameter als Input
> hatte, diese aufgenommen hat und den Rest geliefert hat.
> Hier ist der Rest aber offensichtlich Input (0) , 5 der
> Teiler als 2. Input und als Output kommt die ursprüngliche
> Zahl heraus....oder sehe ich das falsch?

Ich fürchte, das verstehe ich nicht - den ganzen Absatz nicht. Was meinst Du damit? Gib doch mal ein Beispiel.

> War meine Begründung von oben für die 3 eigentlich
> adäquat?

Ja.

> Dann brauche ich noch einen Beweis für die 16. Da hilft
> mir das vorherige Vorgehen offensichtlich nicht mehr
> weiter. Gibt es da einen weiteren Ansatz?

Den Tipp hast Du doch schon bekommen. Schau mal, wie oft die Faktoren durch 2 teilbar sind.

Grüße
reverend


Bezug
                                                
Bezug
Beweise: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 01:08 Do 01.11.2012
Autor: MattiJo


> Hallo MattiJo,
>  
> > Wenn ich es richtig verstehe, folgt dann aus [mm]p^4-1 \equiv 0 mod 5[/mm]
> > dann 5 | [mm]p^4-1[/mm] bzw. ist vielleicht sogar eine äquivalente
> > Schreibweise dafür...??
>  
> Ja, das ist äquivalent.
>  
> >  Reicht das dann als Beweis dafür, dass die 5 [mm]p^4-1[/mm]

> > teilt?
>  
> Ja, das reicht für alle [mm]p\not=5.[/mm]
>  Mit dem "kleinen Fermat" musst Du Dich unbedingt
> auseinandersetzen, den brauchst Du immer wieder. Du musst
> den Satz verstehen, anwenden können und am besten auch
> seinen Beweis jederzeit reproduzieren können. Das ist
> absolut zentrales Wissen in der Zahlentheorie.
>  

Danke für den Hinweis. Ich werde mal nach einer Veranschaulichung suchen, leider taugt mein Skript da nicht wirklich (bin leider kein Mathematiker).

> > Heißt das, dass die Modulo-Operation hier eigentlich die
> > Modulo-Umkehrfunktion ist? Ich kannte Modulo bislang
> > eigentlich immer als Funktion, die zwei Parameter als Input
> > hatte, diese aufgenommen hat und den Rest geliefert hat.
> > Hier ist der Rest aber offensichtlich Input (0) , 5 der
> > Teiler als 2. Input und als Output kommt die ursprüngliche
> > Zahl heraus....oder sehe ich das falsch?
>  
> Ich fürchte, das verstehe ich nicht - den ganzen Absatz
> nicht. Was meinst Du damit? Gib doch mal ein Beispiel.
>  

Da habe ich mich wahrscheinlich mal wieder in einfachen Dingen unverständlich  ausgedrückt, entschuldige bitte.
Ein Beispiel schafft sicher Abhilfe:

Ich kannte Modulo bislang so:

11 mod 4 = 3 ( 11 : 4 = 2 R. 3)
15 mod 3 = 0 (15 : 3 = 5 R. 0)

Das also der Rest zurückgeliefert wird. Hier scheint es umgekehrt zu sein.

>  
> > Dann brauche ich noch einen Beweis für die 16. Da hilft
> > mir das vorherige Vorgehen offensichtlich nicht mehr
> > weiter. Gibt es da einen weiteren Ansatz?
>
> Den Tipp hast Du doch schon bekommen. Schau mal, wie oft
> die Faktoren durch 2 teilbar sind.
>  

Vielen Dank.
p-1 und p+1 sind ja gerade Zahlen, ergo durch 2 teilbar. [mm] p^2+1 [/mm] müsste auch gerade sein (Quadrat einer ungeraden Zahl ist wieder eine ungerade Zahl). Jetzt fehlt mir aber noch ein Faktor 2 (16 = [mm] 2^4), [/mm] d.h. bei einem von den Faktoren müsste ich auf 4 prüfen, anstelle auf 2...


> Grüße
>  reverend
>  


Bezug
                                                        
Bezug
Beweise: Antwort
Status: (Antwort) fertig Status 
Datum: 01:31 Do 01.11.2012
Autor: reverend

Hallo nochmal,

>  >  Mit dem "kleinen Fermat" musst Du Dich unbedingt
> > auseinandersetzen, den brauchst Du immer wieder. [...]
>
> Danke für den Hinweis. Ich werde mal nach einer
> Veranschaulichung suchen, leider taugt mein Skript da nicht
> wirklich (bin leider kein Mathematiker).

Das ist leider nicht sehr anschaulich, aber in der Aussage einfach. Ich bin übrigens auch kein Mathematiker, würde für dieses Geständnis aber nicht mehr das Wort "leider" verwenden. ;-)

> > > Heißt das, dass die Modulo-Operation hier eigentlich die
> > > Modulo-Umkehrfunktion ist? Ich kannte Modulo bislang
> > > eigentlich immer als Funktion, die zwei Parameter als Input
> > > hatte, diese aufgenommen hat und den Rest geliefert hat.
> > > Hier ist der Rest aber offensichtlich Input (0) , 5 der
> > > Teiler als 2. Input und als Output kommt die ursprüngliche
> > > Zahl heraus....oder sehe ich das falsch?
>  >  
> > Ich fürchte, das verstehe ich nicht - den ganzen Absatz
> > nicht. Was meinst Du damit? Gib doch mal ein Beispiel.
>
> Da habe ich mich wahrscheinlich mal wieder in einfachen
> Dingen unverständlich  ausgedrückt, entschuldige bitte.
>  Ein Beispiel schafft sicher Abhilfe:
>  
> Ich kannte Modulo bislang so:
>  
> 11 mod 4 = 3 ( 11 : 4 = 2 R. 3)
>  15 mod 3 = 0 (15 : 3 = 5 R. 0)
>  
> Das also der Rest zurückgeliefert wird. Hier scheint es
> umgekehrt zu sein.

Hm. Dann habe ich es vielleicht doch richtig verstanden. Dein Beispiel ist richtig, nur... - wieso scheint es hier umgekehrt zu sein?

> > > Dann brauche ich noch einen Beweis für die 16. Da hilft
> > > mir das vorherige Vorgehen offensichtlich nicht mehr
> > > weiter. Gibt es da einen weiteren Ansatz?
> >
> > Den Tipp hast Du doch schon bekommen. Schau mal, wie oft
> > die Faktoren durch 2 teilbar sind.
>
>  p-1 und p+1 sind ja gerade Zahlen, ergo durch 2 teilbar.
> [mm]p^2+1[/mm] müsste auch gerade sein (Quadrat einer ungeraden
> Zahl ist wieder eine ungerade Zahl).

Soweit alles richtig. Der Faktor 2*2*2=8 ist also schonmal gesichert.

> Jetzt fehlt mir aber
> noch ein Faktor 2 (16 = [mm]2^4),[/mm] d.h. bei einem von den
> Faktoren müsste ich auf 4 prüfen, anstelle auf 2...

Ja, genau.
Man könnte ja [mm] p^2+1 [/mm] verdächtigen. Da [mm] p\ge2 [/mm] ist, setzen wir also mal $p=2k+1$. Dann ist [mm] p^2+1=4k^2+4k+2 [/mm] und damit sicher nicht durch 4 teilbar.
Also muss (p-1)(p+1) durch 4 teilbar sein. Das ist nun aber leicht zu zeigen. Siehst Du, wie?

Grüße
reverend


Bezug
                                                                
Bezug
Beweise: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 01:47 Do 01.11.2012
Autor: MattiJo


> Hallo nochmal,
>  
> >  >  Mit dem "kleinen Fermat" musst Du Dich unbedingt

> > > auseinandersetzen, den brauchst Du immer wieder. [...]
>  >

> > Danke für den Hinweis. Ich werde mal nach einer
> > Veranschaulichung suchen, leider taugt mein Skript da nicht
> > wirklich (bin leider kein Mathematiker).
>  
> Das ist leider nicht sehr anschaulich, aber in der Aussage
> einfach. Ich bin übrigens auch kein Mathematiker, würde
> für dieses Geständnis aber nicht mehr das Wort "leider"
> verwenden. ;-)
>  

Alles klar ;-)

> > > > Heißt das, dass die Modulo-Operation hier eigentlich die
> > > > Modulo-Umkehrfunktion ist? Ich kannte Modulo bislang
> > > > eigentlich immer als Funktion, die zwei Parameter als Input
> > > > hatte, diese aufgenommen hat und den Rest geliefert hat.
> > > > Hier ist der Rest aber offensichtlich Input (0) , 5 der
> > > > Teiler als 2. Input und als Output kommt die ursprüngliche
> > > > Zahl heraus....oder sehe ich das falsch?
>  >  >  
> > > Ich fürchte, das verstehe ich nicht - den ganzen Absatz
> > > nicht. Was meinst Du damit? Gib doch mal ein Beispiel.
>  >

> > Da habe ich mich wahrscheinlich mal wieder in einfachen
> > Dingen unverständlich  ausgedrückt, entschuldige bitte.
>  >  Ein Beispiel schafft sicher Abhilfe:
>  >  
> > Ich kannte Modulo bislang so:
>  >  
> > 11 mod 4 = 3 ( 11 : 4 = 2 R. 3)
>  >  15 mod 3 = 0 (15 : 3 = 5 R. 0)
>  >  
> > Das also der Rest zurückgeliefert wird. Hier scheint es
> > umgekehrt zu sein.
>  

$ [mm] p^4\equiv [/mm] 1 mod 5 $
$ [mm] p^4-1 \equiv [/mm] 0 mod 5 $

Da ist doch 1 bzw. 0 jetzt der Rest, oder? Und die stehen hier jetzt auf der linken Seite (als Input). Soweit ich es jetzt verstanden habe, sagt doch der kleine Satz von Fermat gerade aus, dass Rest 1 herauskommt bzw. bei Vielfachen der Primzahl Rest 0....

Vielleicht ist es aber einfach auch nur zu spät, und ich erkenne die Modulo-Funktion nicht wieder :-D

> Hm. Dann habe ich es vielleicht doch richtig verstanden.
> Dein Beispiel ist richtig, nur... - wieso scheint es hier
> umgekehrt zu sein?
>  
> > > > Dann brauche ich noch einen Beweis für die 16. Da hilft
> > > > mir das vorherige Vorgehen offensichtlich nicht mehr
> > > > weiter. Gibt es da einen weiteren Ansatz?
> > >
> > > Den Tipp hast Du doch schon bekommen. Schau mal, wie oft
> > > die Faktoren durch 2 teilbar sind.
>  >

> >  p-1 und p+1 sind ja gerade Zahlen, ergo durch 2 teilbar.

> > [mm]p^2+1[/mm] müsste auch gerade sein (Quadrat einer ungeraden
> > Zahl ist wieder eine ungerade Zahl).
>
> Soweit alles richtig. Der Faktor 2*2*2=8 ist also schonmal
> gesichert.
>  
> > Jetzt fehlt mir aber
> > noch ein Faktor 2 (16 = [mm]2^4),[/mm] d.h. bei einem von den
> > Faktoren müsste ich auf 4 prüfen, anstelle auf 2...
>  
> Ja, genau.
>  Man könnte ja [mm]p^2+1[/mm] verdächtigen. Da [mm]p\ge2[/mm] ist, setzen
> wir also mal [mm]p=2k+1[/mm]. Dann ist [mm]p^2+1=4k^2+4k+2[/mm] und damit
> sicher nicht durch 4 teilbar.
>  Also muss (p-1)(p+1) durch 4 teilbar sein. Das ist nun
> aber leicht zu zeigen. Siehst Du, wie?

Ganz unmathematisch würde ich es jetzt mal so formulieren: p ist ja bekanntlich ungerade. Dann sind p-1 und p+1 wie schon erwähnt beide gerade und durch zwei teilbar. Eine von beiden muss aber ja eigentlich durch vier teilbar sein, weil wenn ich zwei aufeinander folgende gerade Zahlen habe, ist immer eine durch zwei, aber die nächste auch durch vier teilbar...
Ist das korrekt so?
(Falls ja, kann man das irgendwie in mathematischer Notation wiedergeben, dass es für einen Beweis taugt?)

Viele Grüße

MattiJo


Bezug
                                                                        
Bezug
Beweise: Antwort
Status: (Antwort) fertig Status 
Datum: 02:13 Do 01.11.2012
Autor: reverend

Hallo MattiJo,

fast fertig. :-)

> > > Ich kannte Modulo bislang so:
>  >  >  
> > > 11 mod 4 = 3 ( 11 : 4 = 2 R. 3)
>  >  >  15 mod 3 = 0 (15 : 3 = 5 R. 0)
>  >  >  
> > > Das also der Rest zurückgeliefert wird. Hier scheint es
> > > umgekehrt zu sein.
>
> [mm]p^4\equiv 1 mod 5[/mm]
>  [mm]p^4-1 \equiv 0 mod 5[/mm]
>  
> Da ist doch 1 bzw. 0 jetzt der Rest, oder? Und die stehen
> hier jetzt auf der linken Seite (als Input). Soweit ich es
> jetzt verstanden habe, sagt doch der kleine Satz von Fermat
> gerade aus, dass Rest 1 herauskommt bzw. bei Vielfachen der
> Primzahl Rest 0....
>  
> Vielleicht ist es aber einfach auch nur zu spät, und ich
> erkenne die Modulo-Funktion nicht wieder :-D

Nein, das ist nicht das Problem. Du denkst offenbar eher programmtechnisch, wie ein Informatiker - Input, Output. So sind diese Äquivalenzen aber nicht gebaut. Die beiden hier oben sind einfach die gleichen Aussagen. Da kommt nichts hinein und nichts heraus, hier wird nur ausgesagt, dass beide Seiten "gleich" oder genauer: einander äquivalent sind. Das heißt, dass bezüglich der Teilbarkeit durch 5 alle andern Primzahlen (und überhaupt alle nicht durch 5 teilbaren Zahlen) in der vierten Potenz den Rest eins lassen. Das ist identisch mit der Aussage, dass deren vierte Potenz minus eins durch 5 teilbar ist.

> > >  p-1 und p+1 sind ja gerade Zahlen, ergo durch 2 teilbar.

> > > [mm]p^2+1[/mm] müsste auch gerade sein (Quadrat einer ungeraden
> > > Zahl ist wieder eine ungerade Zahl).
> >
> > Soweit alles richtig. Der Faktor 2*2*2=8 ist also schonmal
> > gesichert.
>  >  
> > > Jetzt fehlt mir aber
> > > noch ein Faktor 2 (16 = [mm]2^4),[/mm] d.h. bei einem von den
> > > Faktoren müsste ich auf 4 prüfen, anstelle auf 2...
>  >  
> > Ja, genau.
>  >  Man könnte ja [mm]p^2+1[/mm] verdächtigen. Da [mm]p\ge2[/mm] ist,
> setzen
> > wir also mal [mm]p=2k+1[/mm]. Dann ist [mm]p^2+1=4k^2+4k+2[/mm] und damit
> > sicher nicht durch 4 teilbar.
>  >  Also muss (p-1)(p+1) durch 4 teilbar sein. Das ist nun
> > aber leicht zu zeigen. Siehst Du, wie?
>  
> Ganz unmathematisch würde ich es jetzt mal so formulieren:
> p ist ja bekanntlich ungerade. Dann sind p-1 und p+1 wie
> schon erwähnt beide gerade und durch zwei teilbar. Eine
> von beiden muss aber ja eigentlich durch vier teilbar sein,
> weil wenn ich zwei aufeinander folgende gerade Zahlen habe,
> ist immer eine durch zwei, aber die nächste auch durch
> vier teilbar...
>  Ist das korrekt so?

Absolut richtig.

>  (Falls ja, kann man das irgendwie in mathematischer
> Notation wiedergeben, dass es für einen Beweis taugt?)

Klar. Dazu bräuchte man eine Fallunterscheidung. [mm] p\not=2 [/mm] ist ja entweder [mm] p\equiv 1\mod{4} [/mm] oder [mm] p\equiv -1\mod{4}. [/mm] In beiden Fällen ist (p+1)(p-1) durch 4 teilbar.

Einfacher ist es aber, so wie in meiner Behandlung von [mm] p^2+1 [/mm] einfach das Produkt zu untersuchen. [mm] (p+1)(p-1)=p^2-1 [/mm]
Für p=2k+1 (oder auch für p=2k-1) ist [mm] p^2-1 [/mm] durch 4 teilbar, wie man einfach durch Ausmultiplizieren zeigt.

Grüße
reverend


Bezug
        
Bezug
Beweise: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 09:47 Do 01.11.2012
Autor: MattiJo

Aufgabe
827 = 67m + y und 559 = 67n + y mit m,n,y ∈ N die
Aussage 67|  −  für alle n ∈ N

Vielen Dank bisher!
Als nächstes möchte ich die (b) lösen. Sollte der Beweis in diesem Fall mit vollständiger Induktion geschehen? Habe zwei Voraussetzungen und soll damit eine dritte Aussage verifizieren...
Die beiden Hypothesen 827 = 67m + y und 559 = 67n + y mit m,n,y [mm] \in \IN [/mm] sind doch wieder Diophantische Gleichungen, oder?

Bezug
                
Bezug
Beweise: Antwort
Status: (Antwort) fertig Status 
Datum: 10:15 Do 01.11.2012
Autor: abakus


> 827 = 67m + y und 559 = 67n + y mit m,n,y ∈ N die
> Aussage 67|  −  für alle n ∈ N
>  Vielen Dank bisher!
>  Als nächstes möchte ich die (b) lösen. Sollte der
> Beweis in diesem Fall mit vollständiger Induktion
> geschehen? Habe zwei Voraussetzungen und soll damit eine
> dritte Aussage verifizieren...
>  Die beiden Hypothesen 827 = 67m + y und 559 = 67n + y mit
> m,n,y [mm]\in \IN[/mm] sind doch wieder Diophantische Gleichungen,
> oder?

Hallo,
Aus 827=67m+y folgt doch, dass der Rest von 827 bei Teilung durch 67 allein vom Wert y abhängt (denn 67m lässt den Rest 0 bei Teilung durch m.
Mathematischer formuliert heißt das: 827 [mm] $\equiv$ [/mm] y mod 67.
Ebenso gilt 559 [mm] $\equiv$ [/mm] y mod 67.
Kannst du damit was anfangen?

Gruß Abakus



Bezug
                        
Bezug
Beweise: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 10:46 Do 01.11.2012
Autor: MattiJo


>  Aus 827=67m+y folgt doch, dass der Rest von 827 bei
> Teilung durch 67 allein vom Wert y abhängt (denn 67m
> lässt den Rest 0 bei Teilung durch m.
>  Mathematischer formuliert heißt das: 827 [mm]\equiv[/mm] y mod
> 67.
>  Ebenso gilt 559 [mm]\equiv[/mm] y mod 67.
>  Kannst du damit was anfangen?
>  

Leider noch nicht 100%. Ich habe mittlerweile herausgefunden, es gilt für m = n+4 (durch Probieren gefunden), dann kommt stets dasselbe y heraus.

Das mit dem Rest leuchtet mir einigermaßen ein.
Ich habe also nun 67 | 827-y sowie 67 | 559-y.

Nur der nächste Schritt fehlt mir jetzt. Wie schließe ich daraus genau auf 67 | [mm] 827^n [/mm] - [mm] 559^n [/mm] ?


Bezug
                                
Bezug
Beweise: Antwort
Status: (Antwort) fertig Status 
Datum: 11:38 Do 01.11.2012
Autor: abakus


>
> >  Aus 827=67m+y folgt doch, dass der Rest von 827 bei

> > Teilung durch 67 allein vom Wert y abhängt (denn 67m
> > lässt den Rest 0 bei Teilung durch m.
>  >  Mathematischer formuliert heißt das: 827 [mm]\equiv[/mm] y mod
> > 67.
>  >  Ebenso gilt 559 [mm]\equiv[/mm] y mod 67.
>  >  Kannst du damit was anfangen?
>  >  
>
> Leider noch nicht 100%. Ich habe mittlerweile
> herausgefunden, es gilt für m = n+4 (durch Probieren
> gefunden), dann kommt stets dasselbe y heraus.
>  
> Das mit dem Rest leuchtet mir einigermaßen ein.
>  Ich habe also nun 67 | 827-y sowie 67 | 559-y.

Na ja,
weil sowohl 559 als auch 827 kongruent zu y nach dem Modul 67 sind, sind 559 und 827 auch zueinander kongruent.
(Das hätten wir auch kürzer haben können, weil 67 die Differenz 827-559 teilt.)
Für Kongruenzen gibt es nun einige Sätze, z. B. aus [mm] $a\equiv [/mm] b$ mod m folgt [mm] $a^n\equiv b^n$ [/mm] mod m.
Gruß Abakus

>  
> Nur der nächste Schritt fehlt mir jetzt. Wie schließe ich
> daraus genau auf 67 | [mm]827^n[/mm] - [mm]559^n[/mm] ?
>  


Bezug
                                        
Bezug
Beweise: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 12:30 Do 01.11.2012
Autor: MattiJo


> weil sowohl 559 als auch 827 kongruent zu y nach dem Modul
> 67 sind, sind 559 und 827 auch zueinander kongruent.
>  (Das hätten wir auch kürzer haben können, weil 67 die
> Differenz 827-559 teilt.)
>  Für Kongruenzen gibt es nun einige Sätze, z. B. aus
> [mm]a\equiv b[/mm] mod m folgt [mm]a^n\equiv b^n[/mm] mod m.

  
ich versuche es mal mathematisch zu erfassen:

Aus 827 = 67m + y und 559 = 67n + y
folgt

827 [mm] \equiv [/mm]  y mod 67
559 [mm] \equiv [/mm]  y mod 67

folgt

827 [mm] \equiv [/mm] 559 mod 67

Da aus  a [mm] \equiv [/mm] b mod m  [mm] a^n\equiv b^n [/mm] mod m folgt, folgt in diesem Fall

[mm] 827^n \equiv 559^n [/mm] mod 67,

was gleichbedeutend ist zu 67 | [mm] 827^n [/mm] - [mm] 559^n [/mm]

Stimmt das so und ist das ausreichend für einen Beweis?

Bezug
                                                
Bezug
Beweise: Antwort
Status: (Antwort) fertig Status 
Datum: 12:36 Do 01.11.2012
Autor: abakus


> > weil sowohl 559 als auch 827 kongruent zu y nach dem Modul
> > 67 sind, sind 559 und 827 auch zueinander kongruent.
>  >  (Das hätten wir auch kürzer haben können, weil 67
> die
> > Differenz 827-559 teilt.)
>  >  Für Kongruenzen gibt es nun einige Sätze, z. B. aus
> > [mm]a\equiv b[/mm] mod m folgt [mm]a^n\equiv b^n[/mm] mod m.
>  
>
> ich versuche es mal mathematisch zu erfassen:
>  
> Aus 827 = 67m + y und 559 = 67n + y
> folgt
>  
> 827 [mm]\equiv[/mm]  y mod 67
> 559 [mm]\equiv[/mm]  y mod 67
>  
> folgt
>
> 827 [mm]\equiv[/mm] 559 mod 67
>  
> Da aus  a [mm]\equiv[/mm] b mod m  [mm]a^n\equiv b^n[/mm] mod m folgt, folgt
> in diesem Fall
>  
> [mm]827^n \equiv 559^n[/mm] mod 67,

für alle n [mm]\in \IN[/mm]

>  
> was gleichbedeutend ist zu 67 | [mm]827^n[/mm] - [mm]559^n[/mm]
>  
> Stimmt das so und ist das ausreichend für einen Beweis?

Wenn ihr den Satz mit den potenzierten Kongruenzen verwenden dürft, ja.
Gruß Abakus


Bezug
        
Bezug
Beweise: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 13:03 Do 01.11.2012
Autor: MattiJo

Bei der (c) soll ich nun Teilbarkeit des genannten Terms durch 360 nachweisen. Kann ich da ähnlich vorgehen wie bei der a?
360 könnte ich in folgende Faktoren zerlegen:

$ 360 = [mm] 3^2 \cdot [/mm] 5 [mm] \cdot 2^3 [/mm] $

Soll ich jetzt also versuchen, Teilbarkeit durch 5, 8 und 9 nachzuweisen?

Bezug
                
Bezug
Beweise: Antwort
Status: (Antwort) fertig Status 
Datum: 13:14 Do 01.11.2012
Autor: reverend

Hallo MattiJo,

> Bei der (c) soll ich nun Teilbarkeit des genannten Terms
> durch 360 nachweisen. Kann ich da ähnlich vorgehen wie bei
> der a?
>  360 könnte ich in folgende Faktoren zerlegen:
>  
> [mm]360 = 3^2 \cdot 5 \cdot 2^3[/mm]
>  
> Soll ich jetzt also versuchen, Teilbarkeit durch 5, 8 und 9
> nachzuweisen?

Den "genannten Term" kannst Du auch faktorisieren:
[mm] n^2(n^2-1)(n^2-4)=(n-2)*(n-1)*n*n*(n+1)*(n+2) [/mm]

Damit sind die Teilbarkeit durch 5 und 9 leicht zu erledigen.

Die Teilbarkeit durch 8 ist etwas schwieriger, aber man kann zeigen, dass immer einer der drei Faktoren [mm] n^2, (n^2-1) [/mm] und [mm] (n^2-4) [/mm] durch 8 teilbar ist.

Grüße
reverend


Bezug
                        
Bezug
Beweise: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 13:23 Do 01.11.2012
Autor: MattiJo


> Hallo MattiJo,
>  
> > Bei der (c) soll ich nun Teilbarkeit des genannten Terms
> > durch 360 nachweisen. Kann ich da ähnlich vorgehen wie bei
> > der a?
>  >  360 könnte ich in folgende Faktoren zerlegen:
>  >  
> > [mm]360 = 3^2 \cdot 5 \cdot 2^3[/mm]
>  >  
> > Soll ich jetzt also versuchen, Teilbarkeit durch 5, 8 und 9
> > nachzuweisen?
>
> Den "genannten Term" kannst Du auch faktorisieren:
>  [mm]n^2(n^2-1)(n^2-4)=(n-2)*(n-1)*n*n*(n+1)*(n+2)[/mm]
>  
> Damit sind die Teilbarkeit durch 5 und 9 leicht zu
> erledigen.
>  

Okay, dank der Faktorisierung sehe ich jetzt die Teilbarkeit durch 5 sofort, da wir einfach 5 aufeinanderfolgende Zahlen haben und somit eine durch 5 teilbar sein muss.
Nur die 9, die verbirgt sich mir gerade noch...

> Die Teilbarkeit durch 8 ist etwas schwieriger, aber man
> kann zeigen, dass immer einer der drei Faktoren [mm]n^2, (n^2-1)[/mm]
> und [mm](n^2-4)[/mm] durch 8 teilbar ist.
>  

Da fällt mir spontan leider auch nichts dazu ein... :-(

Bezug
                                
Bezug
Beweise: Antwort
Status: (Antwort) fertig Status 
Datum: 13:32 Do 01.11.2012
Autor: reverend

Hallo nochmal,

eine der drei Zahlen (n-2), (n-1) oder n ist durch 3 teilbar.
Ebenso eine der drei Zahlen n, (n+1) oder (n+2).
Soweit die Teilbarkeit durch 9...

Dann mal zur 8.

Für n=4k ist [mm] n^2 [/mm] durch 8 teilbar.
Für n=4k+1 ist [mm] n^2-1 [/mm] durch 8 teilbar.
Für n=4k+2 ist [mm] n^2-4 [/mm] durch 8 teilbar.
Für n=4k+3 ist [mm] n^2-1 [/mm] durch 8 teilbar.

Vielleicht geht das noch einfacher, aber ich sehe nicht so recht, wie.

Grüße
reverend


Bezug
                                
Bezug
Beweise: Antwort
Status: (Antwort) fertig Status 
Datum: 14:27 Do 01.11.2012
Autor: abakus


> > Hallo MattiJo,
>  >  
> > > Bei der (c) soll ich nun Teilbarkeit des genannten Terms
> > > durch 360 nachweisen. Kann ich da ähnlich vorgehen wie bei
> > > der a?
>  >  >  360 könnte ich in folgende Faktoren zerlegen:
>  >  >  
> > > [mm]360 = 3^2 \cdot 5 \cdot 2^3[/mm]
>  >  >  
> > > Soll ich jetzt also versuchen, Teilbarkeit durch 5, 8 und 9
> > > nachzuweisen?
> >
> > Den "genannten Term" kannst Du auch faktorisieren:
>  >  [mm]n^2(n^2-1)(n^2-4)=(n-2)*(n-1)*n*n*(n+1)*(n+2)[/mm]
>  >  
> > Damit sind die Teilbarkeit durch 5 und 9 leicht zu
> > erledigen.
>  >  
>
> Okay, dank der Faktorisierung sehe ich jetzt die
> Teilbarkeit durch 5 sofort, da wir einfach 5
> aufeinanderfolgende Zahlen haben und somit eine durch 5
> teilbar sein muss.
>  Nur die 9, die verbirgt sich mir gerade noch...

Hallo,
wenn n durch 3 teilbar ist und n doppelt vorhanden ist...
Wenn n nicht durch 3 teilbar ist, dann sind unter den 5 aufeinander folgenden Faktoren...

>  
> > Die Teilbarkeit durch 8 ist etwas schwieriger, aber man

Wieso? Unter 5 aufeinanderfolgenden Zahlen sind mindestens zwei Gerade, und jede zweite gerade Zahl ist sogar durch 4 teilbar.

> > kann zeigen, dass immer einer der drei Faktoren [mm]n^2, (n^2-1)[/mm]
> > und [mm](n^2-4)[/mm] durch 8 teilbar ist.
>  >  
>
> Da fällt mir spontan leider auch nichts dazu ein... :-(


Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Zahlentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.vorhilfe.de