|
|
Forum: Ausbildung, Studium & Beruf Frage zu PrimzahlenaufgabeHallo, ich komme mit einer Aufgabe nicht weiter. Es sind paarweise verschiedene Primzahlen gegeben. Außerdem wird a folgendermaßen definiert: a:=1+ Man soll zeigen, dass der kleinste Teiler p(a)>=2 von a eine Primzahl ist mit p(a) {} Ich habe dazu zwei Beispiele durchgerechnet. 1. a:=1+2+3+5=11 p(11)>=2 => p(11)=11 p(11) {2,3,5}
2. a:=1+2+3+5+7=18
p(18)>=2 => p(18)=2
p(18){2,3,5,7}
2. ist dabei ein Widerspruch zu dem, was oben steht. Habe ich einen
Denkfehler?
Ich sehe gerade, die Latex-Formatierungen werden ungünstig angezeigt.
Hier nochmal ohne Latex:
Hallo, ich komme mit einer Aufgabe nicht weiter. Es sind paarweise
verschiedene Primzahlen p_1, p_2, ..., p_n gegeben.
Außerdem wird a folgendermaßen definiert: a:=1+p_1...p_n
Man soll zeigen, dass der kleinste Teiler p(a)>=2 von a eine Primzahl
ist mit
p(a)nicht Element von {p_1, p_2, ..., p_n}
Ich habe dazu zwei Beispiele durchgerechnet.
1. a:=1+2+3+5=11
p(11)>=2 => p(11)=11
p(11) nicht Elemnt von {2,3,5}
2. a:=1+2+3+5+7=18
p(18)>=2 => p(18)=2
p(18)Element von {2,3,5,7}
2. ist dabei ein Widerspruch zu dem, was oben steht. Habe ich einen
Denkfehler?
Bist Du sicher, dass Du die Primzahlen addieren sollst? Ich würde eher vermuten a:=1 + p_1 p_2 ... * p_n (ich meine, die Primzahlen sind zu multiplizieren) :
Bearbeitet durch User
1. Alle Primzahlen sind ungerade! 2. Die Summe einer geraden Anzahl ungerader Zahlen ust immer gerade! 3. Der kleinste Teiler einer geraden Zahl ist immer 2! Zeig am besten die originale Aufgabe! > Man soll zeigen, dass der kleinste Teiler p(a)>=2 von a eine Primzahl > ist Das ist doch die eigentliche Fragestellung? Das heißt ich wähle irgendeine x-beliebige Zahl, die größer oder gleich 2 ist, z.B. 36. Mögliche ganzzahlige Teiler von 36 wären: 36, 18, 9, 6, 3, 1 Per Definition scheidet 1 als kleinster Teiler aus, also ist 3 der kleinste Teiler von 36. Das Spielchen kannst Du mit jeder Zahl machen und 2 oder 3 ist dann der kleinste Teiler und gleichzeitig Primzahl. > 1. Alle Primzahlen sind ungerade!
eine Primzahl ist ein Zahl, die nur 1 und sich selbst teilbar ist.
D.h. 5 und 7 wären auch noch einmal als kleinste Teiler genau einmal
dabei.
Vielen Dank für die vielen Antworten! Günter N. schrieb: > ich meine, die Primzahlen sind zu multiplizieren Danke Günter, dann komme ich schon mal weiter mit der Aufgabe! Woran sieht man denn eigentlich, dass multipliziert werden muss und nicht addiert? heute mal ohne Registrierung schrieb: >> 1. Alle Primzahlen sind ungerade! > eine Primzahl ist ein Zahl, die nur 1 und sich selbst teilbar ist. > D.h. 5 und 7 wären auch noch einmal als kleinste Teiler genau einmal > dabei. 2 Hallo,
mal eine Beweisskizze:
Sei a,b € |N (natürliche Zahlen) mit a > 1 und a*b = 1 + p1*p2*....pn
Angenommen ohne Einschränkung der Allgemeinheit a = p1.
Dann gilt a*b - a*p2*...pn = 1
also
a*(b - p2*...pn) = 1
daraus folgt( wir sind bei den ganzem Zahlen) a = 1 Widerspruch zur
Annahme a > 1.
Also ist a kein Element von {p1,p2,...,pn}
1 + p1*p2*....pn läßt sich in ein Produkt von Primzahlen zerlegen.
Die kleinste Primzahl die in dieser Zerlegung vorkommt ist der kleinste
Teiler p(a).
MfG
egonotto
egonotto schrieb: > 1 + p1*p2*....pn läßt sich in ein Produkt von Primzahlen zerlegen. > Die kleinste Primzahl die in dieser Zerlegung vorkommt ist der kleinste > Teiler p(a). Vielen Dank für deinen Beitrag! Nur das verstehe ich leider nicht ganz. Meiner Überlegung nach müsste doch bei der Division des Terms 1 + p1*p2*....pn durch die jeweilige Primzahl immer der Rest 1 entstehen? Beispielsweise 1+2*3*5=31 => 31:5=6R1. Dann wäre allgemein formuliert immer das Ergebnis des Terms der kleinste Teiler>=2, also hier 31. > 2 falsch > Die kleinste Primzahl die in dieser Zerlegung vorkommt ist der kleinste > Teiler p(a). und was heißt das in der Praxis? 2 oder 3 wird häufiger als kleinster Teiler auftreten und ansonsten ist der kleinste Teiler genau einmal die Primzahl selbst (denn 10,14, usw. sind auch duch 2 statt durch 5 oder 7 teilbar). 61 ist z.B. nur durch 1 und 61 teilbar, per obiger Definition ist damit 61 kleinster Teiler. Also ist der kleinste einmalige Teiler die Primzahl selbst und diese kann unendlich sein. > 31:5=6R1. Dann wäre allgemein formuliert immer das Ergebnis des Terms > der kleinste Teiler>=2, also hier 31. 31 ist eine Primzahl, ansonsten hättest Du 2 als kleinsten Teiler oder 3 bzw. 5 und 7, etc. bei Quadratzahlen. Ich kenne diesen Aufgabentyp nur mit multiplizierten Primzahlen. Wenn sie addiert werden müßten, hast Du ja selbst schon den Beweis geliefert, dass die Aussage nicht stimmt. Nun zur Aufgabe. Du hast ja schon herausgefunden, dass die Zahl a so konstruiert ist, dass keine der gegebenen Primzahlen sie teilt. Du sollst zeigen, dass der kleinste Teiler von a außer der 1 eine Primzahl ist, die nicht in den gegebenen Primzahlen enthalten ist. Fall 1: Die Zahl 2 ist in den gegebenen Primzahlen enthalten. Dann ist a eine ungerade Zahl. 2 ist also kein Teiler. a ist so konstruiert, dass keine der gegebenen Primzahlen a teilt. Also ist a entweder selbst eine Primzahl oder es gibt eine Primfaktorzerlegung, die keine der gegebenen Primzahlen enthält. Fall 2: Die Zahl 2 ist in den gegebenen Primzahlen nicht enthalten. Dann ist a nach Konstruktion eine gerade Zahl (weil alle Primzahlen außer 2 ungerade sind). Damit ist 2 ein Teiler von a. 2 ist auch eine Primzahl, fertig. Hallo,
Also der erste Teil der Beweisskizze zeigt, daß eine Primzahl aus
{p1,p2,...,pn} kein Teiler von 1 + p1*p2*....pn sein kann.
Das entspricht Deinem "Meiner Überlegung nach müsste
doch bei der Division des Terms 1 + p1*p2*....pn durch die jeweilige
Primzahl immer der Rest 1 entstehen?"
Jetzt bleibt noch zu zeigen daß der kleinste Teiler größer 1 von 1 +
p1*p2*....pn (genannt p(1 + p1*p2*....pn)) eine Primzahl ist.
Da p(1 + p1*p2*....pn) ein Teiler von 1 + p1*p2*....pn ist gibt es eine
natürliche Zahl b so daß gilt:
p(1 + p1*p2*....pn) * b = 1 + p1*p2*....pn
Nun kann man jede natürliche Zahl > 1 als Produkt von Primzahlen
schreiben (Primfaktorzerlegung).
Jetzt betrachten wir die Primfaktorzerlegung von p(1 + p1*p2*....pn)
Sei etwa p(1 + p1*p2*....pn) = q1*...*qm mit Primzahlen q1,...qm
dann haben wir:
1 + p1*p2*....pn = q1*...*qm * b
q1 ist also ein Teiler von 1 + p1*p2*....pn
und q1 ist Primzahl und damit q1 > 1
Da aber p(1 + p1*p2*....pn) der kleinste Teiler > 1 von 1 + p1*p2*....pn
muß q1 = p(1 + p1*p2*....pn) sein.
Damit ist nun gezeigt, daß der kleinste Teiler >1 von 1 + p1*p2*....pn
eine Promzahl ist.
MfG
egonotto
Kennst Du den klassischen Beweis, dass es unendlich viele Primzahlen gibt? Wenn nicht, schau ihn dir an (Youtube, z.B., numberphile oder so) und du siehst sofort, woher deine Aufgabe "inspiriert" ist. Die Lösung liegt dann auf der Hand. S. Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.
|
|
Thread beobachten
Seitenaufteilung abschalten