Primzahl

04.11.2017, 21:15

Pythagoras 1235

Auf diesen Beitrag antworten »

Primzahl

Hallo, es geht um folgenden Beweis:

Gegeben seien paarweise verschiedene Primzahlen $\begin{eqnarray*} p_1, p_2, . . . , p_r \end{eqnarray*}$ und $\begin{eqnarray*} a := 1+\prod_{i=1}^r p_i \end{eqnarray*}$
Man zeige: der kleinste Teiler $\begin{eqnarray*} p(a) \geq 2 \end{eqnarray*}$ von a ist eine Primzahl mit $\begin{eqnarray*} p(a) \notin \{ p_1, . . . , p_r\}. \end{eqnarray*}$

Wie kann ich das machen. Was ist die Idee? verwirrt

verwirrt

verwirrt

04.11.2017, 21:19

forbin

Auf diesen Beitrag antworten »

Das läuft auf den Satz von Euklid hinaus, der besagt, dass es unendlich viele Primzahlen gibt.

04.11.2017, 21:22

Leopold

Auf diesen Beitrag antworten »

Das ist die Kernidee für den berühmten Beweis von Euklid für die Unendlichkeit der Primzahlenmenge.

04.11.2017, 21:30

Pythagoras 1235

Auf diesen Beitrag antworten »

Aso ok

smile

Trotzdem.wie soll ich es jetzt anfangen. Es geht ja um den kleinsten Teiler?

04.11.2017, 21:34

Leopold

Auf diesen Beitrag antworten »

Abgesehen vom Teiler 1 ist der kleinste Teiler einer natürlichen Zahl immer eine Primzahl.

04.11.2017, 21:37

Pythagoras 1235

Auf diesen Beitrag antworten »

Aber was muss man noch zeigen. Ich versteh es gerade nicht verwirrt

verwirrt

Anzeige

04.11.2017, 21:43

Leopold

Auf diesen Beitrag antworten »

Nehmen wir einmal die ersten sechs Primzahlen und multiplizieren wir sie miteinander:

$\begin{align*} 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 = 30030 \end{align*}$

Ist dir klar, daß dann $\begin{align*} 30031 \end{align*}$ durch keine dieser Primzahlen teilbar sein kann?

04.11.2017, 21:58

Pythagoras 1235

Auf diesen Beitrag antworten »

Ja das ist mir so dann klar smile

smile

04.11.2017, 22:06

Leopold

Auf diesen Beitrag antworten »

1. Jetzt könnte $\begin{align*} a=30031 \end{align*}$ selbst eine Primzahl sein. Dann wäre abgesehen von 1 ihr kleinster Teil 30031 selbst: $\begin{align*} p(a) = 30031 \not \in \{ 2,3,5,7,11,13 \} \end{align*}$

2. Es könnte auch sein, daß $\begin{align*} a = 30031 \end{align*}$ keine Primzahl ist. Dann gibt es aber eine kleinste Primzahl $\begin{align*} p(a) \end{align*}$ , durch sie teilbar sein muß. Da $\begin{align*} a \end{align*}$ aber durch keine der Zahlen 2,3,5,7,11,13 teilbar ist, muß auch hier gelten: $\begin{align*} p(a) \not \in \{ 2,3,5,7,11,13 \} \end{align*}$

Welcher der beiden Fälle zutrifft, kannst du ja einmal selbst herausfinden.

EDIT
Copy-and-paste-Fehler korrigiert.

04.11.2017, 22:24

Pythagoras 1235

Auf diesen Beitrag antworten »

Das müsste doch 1. sein.

04.11.2017, 22:29

Leopold

Auf diesen Beitrag antworten »

Nein, ist es nicht.

04.11.2017, 23:24

Pythagoras 1235

Auf diesen Beitrag antworten »

Warum kann dem 1 nicht gehen?

05.11.2017, 06:35

Leopold

Auf diesen Beitrag antworten »

Hinter deinen Fragen vermute ich ein Mißverständnis.

* Zunächst ist die Sache mit $\begin{align*} 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 \end{align*}$ nur ein Beispiel, keinesfalls schon der Beweis für den Satz.

* Das Beispiel ist allerdings so gewählt, daß es zum allgemeinen Beweis nur noch ein kleiner Schritt ist. Es ist ein "Beweisbeispiel" und damit fast schon der Beweis.

* Baut man das Beispiel zum allgemeinen Beweis aus, so tritt auch dort der Fall 1. oder der Fall 2. ein. Welcher Fall eintritt, kann im allgemeinen nicht geklärt werden. Es ist aber für den Beweis auch nicht nötig, das zu wissen. Denn egal, welcher Fall eintritt, die Folgerung des Satzes stimmt.

* Im konkreten Beispiel tritt natürlich genau einer der sich gegenseitig ausschließenden Fälle 1. oder 2. ein. Und es ist hier nun einmal nicht 1. Denn 30031 ist keine Primzahl. Du kannst selber einmal nach einem nichttrivialen Teiler suchen, entweder "von Hand" (ein Teiler liegt unter 100) oder durch Verwendung eines Algebra-Programms.

* Bei anderen Beispielen kann tatsächlich der Fall 1. eintreten: $\begin{align*} 2 \cdot 3 + 1 = 7 \end{align*}$ Primzahl! $\begin{align*} 2 \cdot 3 \cdot 5 + 1 = 31 \end{align*}$ Primzahl! $\begin{align*} 2 \cdot 3 \cdot 5 \cdot 7 + 1 = 211 \end{align*}$ Primzahl!

05.11.2017, 19:07

Pythagoras 1235

Auf diesen Beitrag antworten »

Sorry für die späte Antwort. Dann versuche ich mal einen Beweis:

Sei a folgendermaßen definierte Zahl $\begin{eqnarray*} a := 1+ \prod_{i=1}^r p_i \end{eqnarray*}$

Dann kann man 2 Fälle unterscheiden.
1. Fall: a ist eine Primzahl: Dann ist ihr Teiler entweder 1 oder a selbst. Da 1 keine Primzahl ist, ist a ihr kleinster Teiler und dieser ist eine Primzahl. Zudem ist $\begin{eqnarray*} a=p(a) \notin \{p_1,....,p_r\} \end{eqnarray*}$

2. Fall: a ist keine Primzahl. Dann gibt es aber eine kleinsten Teiler, der eine Primzahl ist. Da aber dann a durch kein p_i teilbar ist, weil immer Rest 1 bleiben würde, ist der kleinste Primteiler p(a) $\begin{eqnarray*} p(a) \notin \{p_1,....,p_r\} \end{eqnarray*}$ .

Stimmt das so Leopold verwirrt

verwirrt

05.11.2017, 21:14

Pythagoras 1235

Auf diesen Beitrag antworten »

Kann jmd bitte drübeschauen smile

smile

05.11.2017, 21:27

sibelius84

Auf diesen Beitrag antworten »

Hallo Pythagoras 1235,

es fehlt vielleicht am Anfang noch

"Behauptung: ...

Annahme: ..."

Ist dir klar, warum die Annahme in einen Widerspruch mündet?

Grüße
sibelius84

05.11.2017, 21:46

Pythagoras 1235

Auf diesen Beitrag antworten »

Leider noch nicht irgendwie smile

smile

Die Behauptung ist doch : Die Zahl a besitzt einen kleinsten Teiler p(a) ungleich p_i
Was soll dann die Annahme sein?

05.11.2017, 21:56

sibelius84

Auf diesen Beitrag antworten »

Also, die Behauptung ist das, was du in deinem Initialpost geschrieben hast. Die Annahme in einem Widerspruchsbeweis ist immer das Gegenteil der Behauptung. Kannst du genau formulieren, wie das Gegenteil deiner Behauptung lautet?

a hat nun den kleinsten Teiler p(a). Da gehört der größte (echte) Teiler q(a) zu, sodass a=p(a)q(a).
(Beispiel: 213 hat als kleinsten nichttrivialen Teiler die 3, und als größten die 71. Und 3*71=213.)

Oben habe ich also eine Darstellung von a hingeschrieben. Andererseits hast du für a auch eine Definition aus der Aufgabe. Schreib die mal nebeneinander. Was folgt aus deiner Annahme (des Gegenteils der Behauptung) für p(a), wie kannst du das umschreiben? Sobald du das hast, kannst du deine Gleichung so umformen, dass ein Widerspruch entsteht.

Grüße
sibelius84

05.11.2017, 22:02

Pythagoras 1235

Auf diesen Beitrag antworten »

Die Annahme wäre doch dann: Sei der kleinste Teiler p(a) von a keine Primzahl.

a hat dann Darstellung: $\begin{eqnarray*} a=1+ \prod_{i=0}^n p_i \end{eqnarray*}$ , aber auch $\begin{eqnarray*} a = p(a) * q(a) \end{eqnarray*}$ mit q(a) als größten Teiler.

Weiter komme ich leider nicht. Ich weis nicht mal ob meine Annahme richtig ist. Meine vorigen Beobachtungen waren dann falsch verwirrt

verwirrt

. Ich steh auf dem Schlauch. Tut mir leid verwirrt

verwirrt

unglücklich

06.11.2017, 19:11

Pythagoras 1235

Auf diesen Beitrag antworten »

Kann mir vllt doch noch jmd einen Tipp geben?

06.11.2017, 19:37

sibelius84

Auf diesen Beitrag antworten »

LEMMA

Behauptung:
Der kleinste nichttriviale Teiler einer natürlichen Zahl ist immer eine Primzahl.

Beweis:
Angenommen, n sei eine natürliche Zahl, deren kleinster nichttrivialer Teiler d keine Primzahl ist. Da d keine Primzahl ist, können wir schreiben d=ab mit a, b >= 2. Da a, b >= 2, sind auch a, b < d und beides als Teiler von d auch Teiler von n.
Das ist aber ein Widerspruch dazu, dass d der kleinste nichttriviale Teiler ist. |_|

Augenzwinkern

Augenzwinkern

Dies mal zum Ersten, und zum Zweiten:

Zitat:

" der kleinste Teiler $\begin{eqnarray*} p(a) \geq 2 \end{eqnarray*}$ von a ist eine Primzahl mit $\begin{eqnarray*} p(a) \notin \{ p_1, . . . , p_r\}. \end{eqnarray*}$ "

Deine Behauptung besteht ja noch aus mehr außer "ist eine Primzahl". Vielleicht ist eher das hintere wichtig? Aufgrund meines oben bewiesenen Lemmas bleibt ja nun nicht mehr viel übrig, was man da noch negieren könnte.

06.11.2017, 20:02

Pythagoras 1235

Auf diesen Beitrag antworten »

Danke erstmal smile

smile

Behauptung: Der kleinste Teiler p(a) von a ist eine Primzahl mit $\begin{eqnarray*} p(a) \notin \{p_1,,,p_r\} \end{eqnarray*}$
Dann die Annahme:

Sei der kleinste Teiler von a keine Primzahl und $\begin{eqnarray*} p(a) \in \{p_1,,,p_r\} \end{eqnarray*}$
Das kann ja nach deinem Lemma nicht sein.
Irgendwas scheint falsch. Ich komme einfach nicht weiter Gott

Gott

unglücklich

06.11.2017, 20:13

sibelius84

Auf diesen Beitrag antworten »

Als Annahme, die man zum Widerspruch führen möchte, wählt man typischerweise die aussagenlogische Negation der Behauptung. Wenn die nämlich nicht gelten kann, dann muss die Behauptung gelten - und wir sind fertig! Tanzen

Tanzen

Also:

Deine Behauptung ist:
p(a) ist eine Primzahl UND p(a) ist nicht Element der Menge mit den p_1, ..., p_r.

Aussagenlogische Negation von UND ist ODER - also: Annahme:
p(a) ist keine Primzahl ODER p(a) ist doch Element der Menge mit den p_1, ..., p_r.

Nun kommst du ins Spiel:
Wie ist es mit dem ersten Fall, dass p(a) keine Primzahl ist? Steht das vielleicht im Widerspruch zu etwas, was du kürzlich schon mal gesehen hast?
Also knöpft man sich dann den zweiten Fall vor. Wenn p(a) doch Element der besagten Menge ist - was folgt dann daraus? Wie kannst du p(a) dann schreiben?

06.11.2017, 20:18

Pythagoras 1235

Auf diesen Beitrag antworten »

Sorry ich bin so blöd.(

Also der 1. Fall:

p(a) ist keine Primzahl: Das kann aber nicht sein, denn der kleinste Teiler einer Zahl ist immer eine Primzahl.

2.Fall: p(a) ist doch Element der Menge mit den p_1, ..., p_r.
Dann ist doch a= p(a) * p1....pr oder?

06.11.2017, 20:25

sibelius84

Auf diesen Beitrag antworten »

Zeilen 2, 3, 4 stimmen.

Aber die letzte nicht - denn wie soll das sein? a hat doch eine feste Definition vom Blatt.

Sagen wir mal, ich hätte irgendeine beliebige endliche Menge $\begin{eqnarray*} M=\{m_1,\ldots,m_r\} \end{eqnarray*}$ und ein Element e. Wenn ich nun weiß, dass $\begin{eqnarray*} e\in M \end{eqnarray*}$ , dann weiß ich, dass $\begin{eqnarray*} e=m_j \end{eqnarray*}$ mit einem $\begin{eqnarray*} j\in\{1,\ldots,r\}. \end{eqnarray*}$

06.11.2017, 20:40

Pythagoras 1235

Auf diesen Beitrag antworten »

Aso d.h dann p(a) = p_i mit einem i aus {1,...,r}

D.h $\begin{eqnarray*} a= 1+ \prod_{i=0}^r p_i \end{eqnarray*}$ wobei p_i = p(a) für ein bestimmtes i. Das ist ein Widerspruch zur Voraussetzung. So oder?

06.11.2017, 20:42

sibelius84

Auf diesen Beitrag antworten »

Wo soll denn da der Widerspruch sein? Zu welchem Teil der Voraussetzung genau?

06.11.2017, 20:47

Pythagoras 1235

Auf diesen Beitrag antworten »

p(a) soll doch nicht Element der pi sein. Das war die Behauptung.
Sehe ich was falsch?

06.11.2017, 20:55

sibelius84

Auf diesen Beitrag antworten »

Dass die Annahme, die du zum Widerspruch führen willst, um die Behauptung zu zeigen, der Behauptung widerspricht, ist gerade das Prinzip des Widerspruchsbeweises. Du nimmst das Gegenteil der Behauptung an und zeigst, dass es Quatsch ist.

Um einen Widerspruchsbeweis erfolgreich zu Ende zu führen, muss ein Widerspruch zur Voraussetzung bzw. zur Annahme entstehen.

06.11.2017, 21:00

Pythagoras 1235

Auf diesen Beitrag antworten »

Ja das stimmt. Als ob ich nur 1 Tag studieren würde. Es tut mir leid. Ok
Also wir haben:

Annahme: p(a) ist doch Element der Menge mit den p_1, ..., p_r.

D.h dann p(a) = p_i mit einem i aus {1,...,r},
Wie komme ich zum widerspruch?

06.11.2017, 21:22

sibelius84

Auf diesen Beitrag antworten »

Was war nochmal p(a)q(a)? (...also dann p_i · q(a)?)

Das könntest du mit der Definition von a vom Blatt vergleichen und so umformen, dass da etwas steht, was nicht sein kann. (Es muss ja dann irgendwie damit zu tun haben, dass in der Gleichung nunmehr ein p_i auftaucht, das vorher noch nicht da stand.)

06.11.2017, 21:29

Pythagoras 1235

Auf diesen Beitrag antworten »

Was war nochmal p(a)q(a).
Wenn eine Zahl einen kleinsten Teiler p(a) gibt es einen komplementär Teiler q(a):

Also p_i * q(a)=a für ein i aus {1,...,r}

Für a gilt $\begin{eqnarray*} a := \prod_{i=0}^r p_i \end{eqnarray*}$
Kann ich diese beiden gleichungen dann gleichsetzen?

06.11.2017, 21:41

sibelius84

Auf diesen Beitrag antworten »

J $\begin{eqnarray*} a \end{eqnarray*}$ ! smile

smile

Wobei, du müsstest vielleicht noch in der Summe das i durch ein j ersetzen, weil es doof ist, wenn du das rechts als laufenden Index hast und links als festen.

06.11.2017, 21:52

Pythagoras 1235

Auf diesen Beitrag antworten »

Also dann:
Wenn eine Zahl einen kleinsten Teiler p(a) gibt es einen komplementär Teiler q(a):

Also p_i * q(a)=a für ein i aus {1,...,r}

Für a gilt $\begin{eqnarray*} a := 1+ \prod_{j=0}^r p_j \end{eqnarray*}$

Nach Gleichsetzen folgt: $\begin{eqnarray*} p_i * q(a)=1+ \prod_{j=0}^r p_j \end{eqnarray*}$

Daraus folgt doch p_i teilt die rechte Seite.
Ist das der richtige Schluss?

06.11.2017, 23:32

sibelius84

Auf diesen Beitrag antworten »

Das sieht seeeehr gut aus smile

smile

07.11.2017, 06:55

Pythagoras 1235

Auf diesen Beitrag antworten »

Trotzdem komme ich nicht weiter. Wie sehe ich jetzt meinen Widerspruch?

07.11.2017, 21:35

Pythagoras 1235

Auf diesen Beitrag antworten »

Kann das p_i überhaupt die rechte Seite teilen?

07.11.2017, 21:50

sibelius84

Auf diesen Beitrag antworten »

Ok, dein p_i teilt die rechte Seite, die da wäre

$\begin{eqnarray*} 1+\prod_{j=1}^r p_j \end{eqnarray*}$ .

Aber betrachten wir doch mal

$\begin{eqnarray*} \prod_{j=1}^r p_j (=p_1\ldots p_r). \end{eqnarray*}$ .

Wie kann hier dein p_i eingehen? Wie kommt man dann zum Widerspruch? Ich sehe bereits Licht am Ende des Tunnels, du auch?

07.11.2017, 21:54

Pythagoras 1235

Auf diesen Beitrag antworten »

Ich sehe bereits Licht am Ende des Tunnels, du auch?
Ich will es auch sehen smile

smile

Also

Das p_i ist doch in dem Produkt $\begin{eqnarray*} \prod_{j=0}^r p_j \end{eqnarray*}$ als Faktor enthalten. D.h es teilt dieses. Aner dann kann es nicht $\begin{eqnarray*} 1+ \prod_{j=0}^r p_j \end{eqnarray*}$ teilen. Also Widerspruch
So?

08.11.2017, 22:07

sibelius84

Auf diesen Beitrag antworten »

Genau!

Blumen

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »