Primzahle und Module!

Neue Frage »

Spirit89 Auf diesen Beitrag antworten »
Primzahle und Module!
Hey Leute, ich habe hier folgende Aufgabe, mit der ich echt Schwierigkeiten habe! Bitte helft mir!

Weisen Sie nach:
Für jede ungerade Primzahl gilt : p kongruent 1 (mod 4) oder p kongruent 3 (mod 4)

Iich habe wirklich keine Ahnung wie ich sie lösen soll...

Hier ein paar Gedanken, die ich mir gemacht habe:

- ungerade Primzahl bedeutet doch alle Primzahlen größer als 2

- damit p kongruent 1 (mod 4) gilt, müssen p und 1 ja den gleichen Rest haben, teilt man sie durch 4: Also 1=0*4+1 P müsste dann ja den Rest 1 haben

oder p kongruent 3 (mod 4), dann müsste der Rest 3 sein..

Beispiel: p=3

3 kongruent 3

Beispiel 5:

5 kongruent 1


Ich hoffe soweit ist es schonmal richtig... Aber wie weise ich das nun für alle nach =/ ?
AD Auf diesen Beitrag antworten »

Es gilt sogar

Zitat:
Für jede ungerade Zahl p gilt : p kongruent 1 (mod 4) oder p kongruent 3 (mod 4)
Spirit89 Auf diesen Beitrag antworten »

Das ist toll, nur woher weiß ich das bzw. wie weise ich nach, dass es für jede ungerade Primzahl gilt?
Spirit89 Auf diesen Beitrag antworten »

Wäre es vlt. angebracht, zu beweisen, dass die Behauptung für alle ungeraden Zahlen gilt (z.B. mit Induktion) gilt um dann zu sagen, dass es dann auch für alle ungeraden Primzahlen gilt?
kiste Auf diesen Beitrag antworten »

Das ist gleich schwer zu zeigen da man nur ungerade benutzt, nicht prim.
Welche Darstellung hat eine ungerade Zahl?
Spirit89 Auf diesen Beitrag antworten »

Ist das wirklich gleich schwer? Bei einer ungeraden Primzahl würde mir nämlich noch nicht mal ne Darstellung einer ungeraden Primzahl einfallen..

Eine ungerade Zahl lässt sich auf jeden Fall als 2n-1 darstellen!
 
 
kiste Auf diesen Beitrag antworten »

Und jetzt ist n entweder gerade oder ungerade. Einsetzen der Definition liefert die Behauptung.

Eine ungerade Primzahl kann man natürlich auch als 2n-1 darstellen
Spirit89 Auf diesen Beitrag antworten »

Aber müsste ich nicht dann irgendwas dazuschreiben.. Denn 2n-1 ist ja nicht für jedes n eine Primzahl!

Ich hoffe ich hab dich richtig verstanden: Wenn ich jetzt eine solche Fallunterscheidung mache, kommt ja raus:

2m-1 kongruent 1

m=2a

Das ergibt:

4a-1 kongruent 1 (mod 4)

Nach Regel heißt es ja n | a-b

Kann ich auch machen: n|b-a? Weil dann würde da ja letztlich stehen n| 4a und somit 4|4a, wo ich weiß, dass es stimmt...

m=2a-1

2*(2a-1)-1
4a-2-1
4a-3

Wenn n|b-a auch hier gelten würde, würde sich hier letztlich 4|4a ergeben.. Aber kann man das machen? Wenn ja hab ichs oder?
kiste Auf diesen Beitrag antworten »

Hat ja keiner gesagt dass es für jede Zahl n eine Primzahl ist, aber es existiert eben so eine Zahl.

4n-1 ist nicht kongruent 1 mod 4!

Den Rest verstehe ich nicht, möchte aber darauf hinweisen dass wir uns im Hochschulbereich befinden
Spirit89 Auf diesen Beitrag antworten »

Ist auch unwichtig.. Hab grad gesehen, dass wir es mit Induktion lösen sollen...

IA:

n=2

3 kongruent 3

Behauptung stimmt!

IV: /

IS:

Dann muss sie auch für n+1 stimmen

2(n+1)-1 kongruent 1 oder kongruent 3

2n+1 kongruent 1 oder kongruent 3!

2n-1 + 2 kongruent 1 oder kongruent 3

2n-1 ist kongruent, 2 aber nicht... Somit gilt es nicht für n+1... nOder lieg ich nu komplett falsch?
AD Auf diesen Beitrag antworten »

Mit ziemlichen Erstaunen sehe ich, wie sich dieser Thread entwickelt hat: Die Mücke wächst und wächst, sie hat bereits Elefantengröße - wo führt das noch hin? geschockt
Mystic Auf diesen Beitrag antworten »

Zitat:
Original von Arthur Dent
Mit ziemlichen Erstaunen sehe ich, wie sich dieser Thread entwickelt hat: Die Mücke wächst und wächst, sie hat bereits Elefantengröße - wo führt das noch hin? geschockt


Man könnte aber auch Horaz zitieren mit seinem "Die Berge kreißten und ein Mäuslein ward geboren"... Wenigstens bis jetzt... Big Laugh
Spirit89 Auf diesen Beitrag antworten »

Ja ich gebe euch Recht, die Entwicklung stimmt mich selbst nicht glücklich...

Deswegen nochmal ein Neuanfang ^^

Weisen Sie nach:
Für jede ungerade Primzahl gilt : p kongruent 1 (mod 4) oder p kongruent 3 (mod 4)

Eine ungerade Zahl lässt sich darstellen als: 2n-1

Also: Es soll entweder 2n-1 kongruent 1 (mod 4) oder 2n-1 kongruent 3 (mod 4) gelten!

Ich würde an die Sache nun mit Hilfe der Induktionsregel rangehen!

IA: Ich wähle n=2

So ergibt sich aus 2*2-1 = 3 und es gilt 3 kongruent 3!

IV: Die Behauptung gilt für ein beliebig aber festgewähltes n!

IS: Die Behauptung muss also auch für n+1 gelten...

2(n+1)-1 kongruent 1 oder 3 (mod 4)

also 2n+1 kongruent 1 oder 3 (mod 4)

So bis hierhin... Bin ich aufm richtigen Weg oder lieg ich komplett falsch? Und wenn nicht, wie gehts weiter?
pseudo-nym Auf diesen Beitrag antworten »

Was Arthur insbesondere meint: Man braucht für diesen Beweis keine Induktion.

Alle ungeraden Zahlen lassen sich in der Form darstellen.

Das n ist natürlich und kann entweder gerade, oder ungerade sein. Im ersten Fall hätten wir dann

So und wenn du diese Zahl jetzt modulo 4 betrachtest. Was kommt da raus?
Mystic Auf diesen Beitrag antworten »

Zitat:
Original von pseudo-nym
Was Arthur insbesondere meint: Man braucht für diesen Beweis kein Induktion.


Ja, aber wie der Threadersteller erst unlängst enthüllt hat, ist es Teil der Aufgabenstellung, das mit Induktion zu zeigen... Wäre ja auch sonst zu leicht... Augenzwinkern
Spirit89 Auf diesen Beitrag antworten »

@ pseudo-nym:

Im ersten Fall wäre es 4m + 1 und somit immer der Rest 1

Im zweiten Fall (ungerade): 2(2m+1) +1 = 4m + 3 und somit immer der Rest 3... Somit würde die Behauptung für beide stimmen...

Zur Induktion:

IA: Ich wähle n=1

So ergibt sich aus 2*1+1 = 3 und es gilt 3 kongruent 3!

IV: Die Behauptung gilt für ein beliebig aber festgewähltes n!

IS: Die Behauptung muss also auch für n+1 gelten...

2(n+1)+1 kongruent 1 oder 3 (mod 4)

also 2n+3 kongruent 1 oder 3 (mod 4)

Aber da komm ich einfach net weiter =/
pseudo-nym Auf diesen Beitrag antworten »

Ah, ich seh's gerade, aber warum sollte man denn sowas machen. geschockt

Zeig' doch im Induktionsschritt einfach

Spirit89 Auf diesen Beitrag antworten »

Sorry aber ich verstehe gerade nicht, was du meinst =/
pseudo-nym Auf diesen Beitrag antworten »

Zitat:
Original von Spirit89
Dann muss sie auch für n+1 stimmen

2(n+1)-1 kongruent 1 oder kongruent 3

2n+1 kongruent 1 oder kongruent 3!


Richtig aufgeschrieben, heißt da nichts anderes als


Wenn du nun die beiden Aussagen aus meinem letzen Post zeigst, dann hast du auch diese Aussage bewiesen.
Spirit89 Auf diesen Beitrag antworten »

Kann ich das mit einer Fallunterscheidung machen?

Also für 2(n+1) + 1 => n=2a => 4a + 2 + 1 => 4a + 3 => kongruent zu 3 modulo 4 da beide den Rest 3 haben

Für 2(n+1) + 1 => n=2a+1 => 4a + 4 + 1 => 4a + 5

?
pseudo-nym Auf diesen Beitrag antworten »

Die Fallunterscheidung ist überflüssig. Multiplizier' einfach aus.
Spirit89 Auf diesen Beitrag antworten »

Dann steht da 2n+3 kongruent 1 (mod 4) oder 2n+3 kongruent 1 (mod 4)

Aber das bringt mich net weiter.. Sry steh völlig aufm Schlauch!
pseudo-nym Auf diesen Beitrag antworten »

Also wenn ich ausmulitipliziere, bekomme ich

Spirit89 Auf diesen Beitrag antworten »

Wobei die Behauptung ja schon einmal für 2n+1 laut Voraussetzung gilt... Aber wie ist es mit dem "+2" ?
pseudo-nym Auf diesen Beitrag antworten »

Zitat:
Original von Spirit89
Wobei die Behauptung ja schon einmal für 2n+1 laut Voraussetzung gilt.


Und was ist diese Behauptung?
Spirit89 Auf diesen Beitrag antworten »

Dass, teilt man durchg 4 entweder der Rest 1 bleibt oder der Rest 3...
Spirit89 Auf diesen Beitrag antworten »

Ich häng leider am Ende... Diese "+2" ... Wie kann ch zeigen, dass auch das laut Voraussetzung gilt =/ ?
pseudo-nym Auf diesen Beitrag antworten »


Du willst doch diese Implikation zeigen und die Vorrassetzung dieser Implikation ist . Das musst du bei

benutzen.
Spirit89 Auf diesen Beitrag antworten »

Bedeutet es vlt., dass da laut Voraussetzung schon für 2n+1 gilt, dass der Rest 1 ist, für 2n+1+2 gilt, dass der Rest 3 ist?n Ich hab keine Ahnung...
pseudo-nym Auf diesen Beitrag antworten »

ja, klar du hast

wenn jetzt gilt, dann kannst du einfach einsetzen. Also

und damit ist die Behauptung bewiesen.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »