www.vorhilfe.de
- Förderverein -
Der Förderverein.

Gemeinnütziger Verein zur Finanzierung des Projekts Vorhilfe.de.
Hallo Gast!einloggen | registrieren ]
Startseite · Mitglieder · Impressum
Forenbaum
^ Forenbaum
Status VH e.V.
  Status Vereinsforum

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Suchen
 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
Weitere Fächer:

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

Primzahlbeweis mit Kongruenz: Aufgabe
Status: (Frage) beantwortet Status 
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

        
Bezug
Primzahlbeweis mit Kongruenz: Antwort
Status: (Antwort) fertig Status 
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


Bezug
                
Bezug
Primzahlbeweis mit Kongruenz: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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

Bezug
                        
Bezug
Primzahlbeweis mit Kongruenz: Antwort
Status: (Antwort) fertig Status 
Datum: 13:40 Di 13.12.2011
Autor: reverend

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


Bezug
                                
Bezug
Primzahlbeweis mit Kongruenz: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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  


Bezug
                                        
Bezug
Primzahlbeweis mit Kongruenz: Antwort
Status: (Antwort) fertig Status 
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

Bezug
                                                
Bezug
Primzahlbeweis mit Kongruenz: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
                                                
Bezug
Primzahlbeweis mit Kongruenz: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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?


Bezug
                                                        
Bezug
Primzahlbeweis mit Kongruenz: Antwort
Status: (Antwort) fertig Status 
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?
>  


Bezug
                                                                
Bezug
Primzahlbeweis mit Kongruenz: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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

Bezug
                                                                        
Bezug
Primzahlbeweis mit Kongruenz: Antwort
Status: (Antwort) fertig Status 
Datum: 19:20 Di 13.12.2011
Autor: reverend

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


Bezug
                                
Bezug
Primzahlbeweis mit Kongruenz: Frage (reagiert)
Status: (Frage) reagiert/warte auf Reaktion Status 
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.

Bezug
                                        
Bezug
Primzahlbeweis mit Kongruenz: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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



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


^ Seitenanfang ^
ev.vorhilfe.de
[ Startseite | Mitglieder | Impressum ]