mikrocontroller.net

Forum: Ausbildung, Studium & Beruf Frage zu Primzahlenaufgabe


Autor: Thomas Reil (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo, 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?

Autor: Thomas Reil (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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?

Autor: Günter Nowinski (turtle64)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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
Autor: Max Mustermann (jens2001)
Datum:

Bewertung
-1 lesenswert
nicht lesenswert
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!

Autor: Bilen (Gast)
Datum:

Bewertung
2 lesenswert
nicht lesenswert
Max M. schrieb:

> 1. Alle Primzahlen sind ungerade!

Seit wann?

Autor: heute mal ohne Registrierung (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> 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.

Autor: heute mal ohne Registrierung (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> 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.

Autor: heute mal ohne Registrierung (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
sowie die restlichen Primzahlen

Autor: Thomas Reil (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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?

Autor: EyeRoll (Gast)
Datum:

Bewertung
2 lesenswert
nicht lesenswert
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

Autor: egonotto (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Thomas Reil (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: heute mal ohne Registrierung (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> 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.

Autor: heute mal ohne Registrierung (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> 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.

Autor: Günter Nowinski (turtle64)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Thomas Reil (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Super, danke Günter, jetzt habe ich es verstanden!

Autor: egonotto (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Stefan (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.