Beweise < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | 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?
|
|
| |
|
| Status: |
(Antwort) fertig  | | 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?
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | 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?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | 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?
>
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | 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.
|
|
|
| |
|
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
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | 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
>
|
|
|
| |
|
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
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | 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
|
|
|
| |
|
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
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | 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?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | 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
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | 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] ?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | 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] ?
>
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | 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?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | 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
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | 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?
|
|
|
| |
|
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
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | 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... :-(
|
|
|
| |
|
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
|
|
|
| |
|
| Status: |
(Antwort) fertig | | 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... :-(
|
|
|
|
