Primzahlbeweis mit Kongruenz < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:07 Mo 12.12.2011 | | Autor: | HannSG |
| Aufgabe | | Zeigen Sie mittels Kongruenz: Ist [mm] n\in \IN, [/mm] so ist [mm] 4*14^{n}+1 [/mm] keine Primzahl. |
Meine Idee:
m | [mm] 4*14^{n}+1 [/mm]
dann ist zu zeigen: [mm] 4*14^{n}+1\equiv0 [/mm] mod m
Aber wie soll ab da dann die Umformung aussehen? Ich weiß ja nicht was m ist.
Liebe Grüße,
HannSG
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:36 Mo 12.12.2011 | | Autor: | felixf |
Moin!
> Zeigen Sie mittels Kongruenz: Ist [mm]n\in \IN,[/mm] so ist
> [mm]4*14^{n}+1[/mm] keine Primzahl.
> Meine Idee:
>
> m | [mm]4*14^{n}+1[/mm]
> dann ist zu zeigen: [mm]4*14^{n}+1\equiv0[/mm] mod m
>
> Aber wie soll ab da dann die Umformung aussehen? Ich weiß
> ja nicht was m ist.
Probier es doch mal fuer konkrete kleine $m$. Etwa fuer $m = 3$ und $m = 5$. Kannst du in beiden Faellen sagen, fuer welche $n$ es keine Primzahl sein kann?
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:26 Di 13.12.2011 | | Autor: | HannSG |
Hallo.
Für m=3 ist [mm] 4*14^{n}+1 [/mm] mit n=ungeraden keine Primzahl.
Für m=5 ist [mm] 4*14^{n}+1 [/mm] mit n=gerade keine Primzahl.
Das kann ich natürlich nur vermuten, da ich ja nicht alle Zahlen testen kann.
Mir ist leider trotzdem noch unklar wie ich allgemeingültig beweisen kann, dass [mm] 4*14^{n}+1 [/mm] keine Primzahl ist.
Vielen Danke schonmal.
Lg HannSG
|
|
|
| |
|
Hallo HannSG,
> Für m=3 ist [mm]4*14^{n}+1[/mm] mit n=ungeraden keine Primzahl.
> Für m=5 ist [mm]4*14^{n}+1[/mm] mit n=gerade keine Primzahl.
>
> Das kann ich natürlich nur vermuten, da ich ja nicht alle
> Zahlen testen kann.
Quatsch. Das kannst Du beides ganz einfach vollständig zeigen. Es genügt doch eine Restklassenbetrachtung zu den beiden Modulen.
> Mir ist leider trotzdem noch unklar wie ich
> allgemeingültig beweisen kann, dass [mm]4*14^{n}+1[/mm] keine
> Primzahl ist.
Na, damit hast Du doch schonmal gezeigt, dass n weder gerade noch ungerade sein darf.
Reicht das nicht? Oder fallen Dir natürliche Zahlen ein, die weder gerade noch ungerade sind?
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:20 Di 13.12.2011 | | Autor: | HannSG |
> Na, damit hast Du doch schonmal gezeigt, dass n weder
> gerade noch ungerade sein darf.
> Reicht das nicht? Oder fallen Dir natürliche Zahlen ein,
> die weder gerade noch ungerade sind?
Nein das jetzt nicht, aber ist damit auch beweisen, dass das für alle m gilt und nicht nur für m=3 und m=5?
Danke. :)
LG
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:33 Di 13.12.2011 | | Autor: | abakus |
Hallo, wenn du einige Beispiele ausrechnest, wirst du feststellen, dass der Term entweder durch 3 oder durch 5 teilbar ist.
Betrachte beide Fälle (n gerade bzw. ungerade) getrennt und weise im jeweiligen Fall die Teilbarkeit durch 5 bzw. 3 allgemein (mit Hilfe von Kongruenzen) nach.
Gruß Abakus
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:50 Di 13.12.2011 | | Autor: | abakus |
Hallo,
sei n gerade. Dann kann man n=2*k setzen, und [mm] $14^n=14^{2k}=196^k$.
[/mm]
Nun gilt [mm] $196\equiv [/mm] 1 mod 5$.
Was gilt dann
- für [mm] $196^k$
[/mm]
- für [mm] $4*196^k$
[/mm]
- für [mm] $4*196^k+1$
[/mm]
(jeweils mod 5)?
Gruß Abakus
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:44 Di 13.12.2011 | | Autor: | HannSG |
Ich hab das für n=gerade mit mod 5 mal gemacht und das klappt auch soweit.
[mm] 196^{k} \equiv [/mm] 1 mod 5 gilt [mm] \forall k\in\IN
[/mm]
[mm] 4*196^{k} \equiv [/mm] 1 mod 5 gilt nicht (ist nicht [mm] \equiv)
[/mm]
[mm] 4*196^{k}+1 \equiv [/mm] 0 mod 5 gilt [mm] \forall k\in\IN
[/mm]
aber beim letzten ist es dann 0 mod 5. das kann man doch nicht einfach machen, oder? und wenn ich die eins durch equivalenzumformung rüber hole, müsste da ja -1 stehen, oder sehe ich das falsch?
bei n=ungerade für m=3 klappt das so auch nicht.
[mm] 14^{n}=14^{2k-1}=196^{k-1}
[/mm]
[mm] 196^{k-1} \equiv [/mm] 1 mod 3 gilt [mm] \forall k\in\IN
[/mm]
[mm] 4*196^{k-1} \equiv [/mm] 1 mod 3 gilt [mm] \forall k\in\IN
[/mm]
[mm] 4*196^{k-1}+1 \equiv [/mm] 0 mod 3 gilt nicht (ist nicht [mm] \equiv)
[/mm]
und das macht ja keinen sinn.
wo ist mein fehler?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:53 Di 13.12.2011 | | Autor: | abakus |
> Ich hab das für n=gerade mit mod 5 mal gemacht und das
> klappt auch soweit.
>
> [mm]196^{k} \equiv[/mm] 1 mod 5 gilt [mm]\forall k\in\IN[/mm]
> [mm]4*196^{k} \equiv[/mm] 1 mod 5 gilt nicht (ist nicht [mm]\equiv)[/mm]
Aber aus
[mm]196^k\equiv [/mm] 1 mod 5 folgt doch
[mm]4*196^k\equiv [/mm] 4*1 mod 5!
Für den nächsten Schritt addiere 1 auf beiden Seiten.
Gruß Abakus
> [mm]4*196^{k}+1 \equiv[/mm] 0 mod 5 gilt [mm]\forall k\in\IN[/mm]
>
> aber beim letzten ist es dann 0 mod 5. das kann man doch
> nicht einfach machen, oder? und wenn ich die eins durch
> equivalenzumformung rüber hole, müsste da ja -1 stehen,
> oder sehe ich das falsch?
>
> bei n=ungerade für m=3 klappt das so auch nicht.
>
> [mm]14^{n}=14^{2k-1}=196^{k-1}[/mm]
Das ist ganz ungünstig. Schreibe lieber n als 2k PLUS 1.
Du erhältst [mm]14^{n}=14^{2k+1}=14^1*14^{2k}=14*196^k[/mm]
>
> [mm]196^{k-1} \equiv[/mm] 1 mod 3 gilt [mm]\forall k\in\IN[/mm]
> [mm]4*196^{k-1} \equiv[/mm]
> 1 mod 3 gilt [mm]\forall k\in\IN[/mm]
> [mm]4*196^{k-1}+1 \equiv[/mm] 0 mod 3
> gilt nicht (ist nicht [mm]\equiv)[/mm]
>
> und das macht ja keinen sinn.
> wo ist mein fehler?
>
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:14 Di 13.12.2011 | | Autor: | HannSG |
bei n=gerade klappt das jetzt.
muss bei n=ungerade dann [mm] 14*196^{k} \equiv [/mm] 14 mod 3 stehen?
dann würde das auch klappen. :)
kann ich dann einfach schlussfolgern:
da [mm] 4*14^{n}+1 [/mm] für n gerade und ungerade (n [mm] \in\IN) [/mm] teilbar ist, ist [mm] 4*14^{n}+1 [/mm] keine Primzahl.
Vielen Dank für die Hilfe!
Das hat mir sehr geholfen!
Liebe Grüße,
HannSG
|
|
|
| |
|
Hallo nochmal,
> bei n=gerade klappt das jetzt.
Bei der Betrachtung [mm] \mod{5}, [/mm] hoffe ich. 
> muss bei n=ungerade dann [mm]14*196^{k} \equiv[/mm] 14 mod 3
> stehen?
> dann würde das auch klappen. :)
Das ist richtig, aber doch nur ein Zwischenschritt. Am Ende musst Du doch zeigen, dass [mm] 14^{2k+1}\equiv -1\mod{3} [/mm] ist.
> kann ich dann einfach schlussfolgern:
>
> da [mm]4*14^{n}+1[/mm] für n gerade und ungerade (n [mm]\in\IN)[/mm] teilbar
> ist, ist [mm]4*14^{n}+1[/mm] keine Primzahl.
Ja, genau.
Ein Wermutstropfen bleibt. Je nachdem, wie Ihr [mm] \IN [/mm] definiert habt, könnte noch der Fall n=0 ärgern. Da gibt es nämlich doch eine Primzahl...
> Vielen Dank für die Hilfe!
> Das hat mir sehr geholfen!
Na, das ist die Hauptsache.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 16:33 Di 13.12.2011 | | Autor: | HannSG |
> Quatsch. Das kannst Du beides ganz einfach vollständig
> zeigen. Es genügt doch eine Restklassenbetrachtung zu den
> beiden Modulen.
Wie funktioniert so eine Restklassenbetrachtung? Ich glaube das haben wir nicht gemacht.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:01 Di 13.12.2011 | | Autor: | felixf |
Moin!
> > Quatsch. Das kannst Du beides ganz einfach vollständig
> > zeigen. Es genügt doch eine Restklassenbetrachtung zu den
> > beiden Modulen.
>
> Wie funktioniert so eine Restklassenbetrachtung? Ich glaube
> das haben wir nicht gemacht.
Schau dir mal die Mitteilung von abakus an.
LG Felix
|
|
|
|
