Warum geht man beim Beweis von es gibt unendlich viele Primzahlen so vor?

Man addiert alle Primzahlen miteinander bis Pn (die letzte Primzahl) und addiert dann auf diese Summe noch eine eins und zeigt dass da eine Primzahl ist. Ich verstehe nicht, wieso wenn man endlich viele Primzahlen addiert und eine eins hinzufügt eine Primzahl bekommt oder habe ich da was falsch verstanden?

5 Antworten

JuIi69

Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer

Mathematik

05.10.2021, 18:02

Man addiert die Primzahlen nicht, man multipliziert die Primzahlen und addiert anschließend 1.

Denkschulen

Fragesteller

05.10.2021, 18:03

Ok aber warum kommt dann Zwangsläufig eine Primzahl dann raus wenn man das macht?

eterneladam

Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer

Mathematik

05.10.2021, 18:14

Man multipliziert alle Primzahlen bis zu einen angenommenen grössten und addiert 1. Diese Zahl ist durch keine der im Produkt enthaltenen Primzahlen teilbar Das heisst nicht, dass sie selbst Primzahl sein muss! Sie könnte auch durch eine Primzahl teilbar sein, die grösser ist als die angenommene grösste. In beiden Fällen hat man einen Widerspruch zur Annahme, es gäbe nur endlich viele Primzahlen.

Denkschulen

Fragesteller

05.10.2021, 18:15

Aber warum genau ist das ein Widerspruch wenn die neue Zahl keine Primzahl wäre

eterneladam

05.10.2021, 18:24

@Denkschulen

Weil diese neue Zahl dann zerlegbar in Primzahlen sein muss (wenn sie nicht selbst schon prim ist), aber keine in dieser Zerlegung kommt in der angenommenen Liste vor (sonst wäre 1 durch diese Primzahl teilbar). Also hat man doch neue Primzahlen gefunden, was ein Widerspruch zur Annahme ist.

Jangler13

Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer

Mathematik

05.10.2021, 19:35

Das Ergebnis ist keine Primzahl, sondern eine Zahl die durch keine der gegebenen Primzahlen geteilt werden kann.

Sei nämlich p eine beliebige der endlichen Primzahlen und q das Produkt der anderen.

Angenommen p*q+1 ist durch p teilbar.

Es ist offensichtlich dass p*q durch teilbar ist.

Dann muss aber auch p*q+1-p*q=1 durch p teilbar sein, das ist nur für p=1 der Fall, 1 ist aber nicht prim.

Somit teilt jede der "endlich vielen" Primzahlen p*q+1 nicht. Es muss also noch eine Primzahl geben, die diese Zahl Teilt (es kann auch die Zahl selbst sein, muss aber nicht)

Wenn man jetzt die neu gefundene Primzahl zu der Menge der "endlichen Primzahlen" hinzufügt, kann man den Prozess wiederholen und noch eine Primzahl finden.

Und das funktioniert unendlich oft.

Tannibi

Nutzer, der sehr aktiv auf gutefrage ist

im Thema Mathematik

05.10.2021, 18:03

Man addiert sie nicht, sondern multipliziert sie.
Nur die 1 wird addiert. Wenn man das dann durch
irgendeine Primzahl teilt, bleibt immer 1 als Rest.
Das ist die Definition einer Primzahl: Nicht durch
Primzahlen teilbar.

Rowal

05.10.2021, 18:19

Wenn es nur endlich viele gäbe könnte man diese alle multiplizieren und 1 hinzuaddieren und erhält eine Zahl N. Das Ergebnis ist nicht notwendigerweise eine Primzahl, aber sie ist durch keine der Primzahlen des Produkts teilbar, weil ja immer ein Rest 1 bleibt. Die Primfaktoren der Zahl N sind also andere Primzahlen. Auf diese Weise kann man immer neue Primzahlen finden, indem man alle bekannten multipliziert, 1 addiert und von dieser Zahl die Primfaktoren ermittelt.

Ähnliche Fragen

Beweis Primzahlen?

Bei dem Beweis, dass es unendlich viele Primzahlen gibt, geht man ja von einer größten Primzahl aus, die die Summe aller Primzahlen plus 1 ist. Meine Frage ist nun woher diese 1 kommt und warum man sie hier addiert.

...zur Frage

ungerade primzahlen?

eine primzahl ist durch sich selbst und durch 1 teilbar. gibt es endlich oder unendlich viele ungerade primzahlen? meiner meinung nach unendlich viele, oder hört die reihe irgendwann auf?

...zur Frage

Ist jede gerade Zahl Summe zweier Primzahlen?

Mein Vorschlag wäre ein LGS mit

10 = 12Y + 8X

14 = 16Y + 20X

Wodurch hier die Summe zweier geraden Zahlen durch gerade Zahlen gebildet wird, die nicht Primzahlen sind.

Ich erhalte auch für X = 11/14 und Y = 1/14

Wodurch doch bewiesen wäre, dass es zumindest zwei gerade Zahlen gibt, die nicht durch die Summe zweier Primzahlen gebildet werden.

Hab mich sicherlich irgendwo getäuscht. Der "Beweis" ist ja auch zu simpel. Deswegen meine Frage: Wie kann man das Beweisen?

...zur Frage

Primzahl?

ich bin 10. klasse und weiß einfach nicht was eine primzahl ist.

primzahlen kann man durch eins und sich selbst teilen, sie sind größer als 1 und sind ganze zahlen. Das weiß ich, aber irgendwie habe ich richtigen denkfehler.

2 durch 1 ist 2, 2 durch sich selbst ist doch 1.

3 durch 1 ist 3, 3 durhc sich selbst also 3 ist doch 1

4 durch 1 ist 4, 4 durch sich selbst (4 ist doch 1)

bin 10. und fühl mich richtig dämlich.

häää

...zur Frage

Primzahlbrüche

Außer 1/2 = 0,5 und 1/5 = 0,2 haben alle Brüche 1/Primzahl, die ich kenne, eine periodische Dezimaldarstellung.

Gilt das grundsätzlich für alle Primzahlen, und gibt es ggf. dazu einen (einfachen) Beweis?

(Dass es für 2 und 5 nicht gilt, liegt wohl daran, dass dies die Teiler von 10 sind, der Basis unseres Zahlsystems.)

...zur Frage

Mathe Vera?

Christian erklärt seine Regel mit der Primzahlen finden möchte: "ich verdopple eine Primzahl dann nehme ich diese verdoppelte Primzahl und addiere einmal eins und einmal subtrahiere ich einst so heiß ich zwei Zahlen von den mindestens einer dieser Zahlen eine Primzahl ist" stimmt Christiansregel?

...zur Frage

Zahlentheorie: n-te Primzahl < exp(2^(n-1))?

Hallo, ich soll obige Ungleichung mittels Induktion unter Verwendung von Euklids Beweis zur Unendlichkeit der Primzahlen zeigen. (Also der Beweis mit dem Produkt aller "endlichen" Primzahlen +1 wobei man dann zeigt, dass dieser Term einen Primteiler hat, der nicht in der endlichen Abzählung vorkommt)

If p_n denotes the n-th prime (in ascending order), deduce by induction from Euclid’s proof of Theorem 1.2 that p_n < exp(2^(n−1)).

Ich habe diese Ungleichung auch bewiesen, aber ehrlich gesagt finde ich meinen Beweis sehr unschön, finde aber keine Verbesserung, auch wenn ich schon mehrere Stunden an der Aufgabe sitze. Mein Beweis per Induktion:

Indunktionsvoraussetzung mit n=1 ist klar. Induktionsannahme auch. Zum Induktionsschluss:

Sei p1,..,pn eine Abzählung der ersten n Primzahlen. Es gilt, dass p1p2..pn+1 einen Primteiler q hat, der noch nicht in dieser Abzählung vorkommt (das ist gerade der Beweis von Euklid zur Unendlichkeit). Da p1,..,pn die ersten n Primzahlen repräsentiert, folgt dass p(n+1) die kleine Primzahl ist, die ein Teiler von p1..pn+1 sein kann (insbesondere kann p1..pn+1 selbst prim sein).

Daraus folgt insgesamt p(n+1)<=p1..pn+1

Nun setze ich die Induktionsvoraussetzung ein und fasse zusammen:

p1..pn + 1 < exp(2^0)exp(2^1)...exp(2^(n-1)) + 1 =
exp(2^0 + 2^1 + ... + 2^(n-1)) +1

Nun erkennt man, dass im Exponenten gerade die geometrische Summe mit x=2 von k=0 bis n-1 steht. Diese Summe entspricht (1-2^n)/(1-2). Das lässt sich vereinfachen zu (2^n - 1 )

Insgesamt folgt bis hierhin:

p(n+1) < 1 + exp(2^n - 1)

Nun zu dem Schritt, der mir selbst absolut nicht gefällt.

Ich zeige, dass das weglassen der +1 vorne und der -1 in der e-Funktion sich so wegheben, dass die ungleichheit erhalten bleibt, also explizit zeige ich dass gilt:

1 + exp(2^n - 1) < exp(2^n) (womit ich fertig wäre)

Ich zeige das so:

1 + exp(2^n - 1) = 1 + exp(2^n)/e = 1/e * (e + exp(2^n))

Es folgt also :

1/e * (e + exp(2^n)) < exp(2^n)

Mit Äquivalenzumformung erhalte ich:

e + exp(2^n) < e * exp(2^n)

Da diese Aussage für n=1 gilt und die Ableitung der e-Funktion die e-Funktion selbst ist, also insbesondere die Ableitung monoton steigt, vergrößert sich der Abstand sogar für alle n>1.

Wie gesagt, dieser letzte Teil gefällt mir gar nicht und ich wäre froh, wenn mir jemand eine alternative und schönere Argumentation bereitstellen könnte.

MfG

...zur Frage

Warum ist 30031 keine Primzahl?

Eigentlich ist doch jede Zahl, für welche folgendes gilt, eine Primzahl: M=p1*p2*...pn+1 (p steht für Primzahl). Dies folgt meines Erachtens nach aus dem Satz von Euklid. Die Zahl M ist entweder eine Primzahl oder eben keine. Wenn es keine ist, muss es durch wenigstens einen Primfaktor teilbar sein, dies aber wegen der 1.

Dieses Muster geht bis zu 2*3*5*7*11+1 auch auf, aber bei 2*3*5*7*11*13+1 nicht mehr. 2*3*5*7*11*13+1= 30031. Wenn ich die Zahl 30031 in so einen Primzahlen-Test eingebe, kommt da raus, dass es sich dabei um keine Primzahl handelt, weil sie irgendwie noch die 59 und was anderes als Teiler hat.

Wie kann das sein?

...zur Frage

Primzahlen berechnen

will man zum Beispiel bei Visual Basic ein Programm schreiben, dass überprüft, ob Zahlen Primzahlen sind, macht man das mit einer Schleife, die von 2 bis zur Wurzel der Zahl geht. Meine Frage ist jetzt, warum man die Schleife nur bis zur Wurzel der Zahl machen muss? Ich habe gelesen, dass es nur Teiler bis zu der Wurzel geben kann aber warum ist das so? Ich habe leider keine der Erklärungen verstanden >.<

Hier nochmal mein Code zur Verständnis:

Dim p As Long = tbPrimzahl.Text
Dim Counter As Long
    Dim Primzahl As Boolean  = True                            

        For Counter = 2 To  Math.Sqrt(p) Step 1
            If p Mod Counter = 0 And Counter <> 1 Then
              Primzahl = False
              MsgBox(p & " ist keine Primzahl.", MsgBoxStyle.OkOnly)
              Exit Sub
            End If
        Next Counter

...zur Frage

Beweis, dass die Primzahlen abzählbar unendlich sind

Wie lässt sich Beweisen, dass die Primzahlen abzählbar unendlich sind? LG

...zur Frage

Gibt es unendlich viele ganze Zahlen n mit der Eigenschaft, dass n² - 1 durch höchstens zwei verschiedene Primzahlen teilbar ist, gleichzeitig aber nicht durch?

das Quadrat einer ungeraden Primzahl?

...zur Frage

Wurzel jeder Primzahl irrational?

Die Frage stimmt für die ersten beiden Primzahlen. Wurzel 2 und Wurzel 3 sind irrational. Gilt die Frage für jede Primzahl? Kennt jemand ein Beweis dazu?

...zur Frage

"Primzahlen-prüfer" programmier (C#)?

Das Programm wurde in c# programmiert. Ich wollte ein etwas programmieren, das die Startzahl (endlos) immer um 1 addiert und prüft ob diese Zahl eine Primzahl ist oder nicht. Habe den Quellcode unter diesem Text geschrieben, aufm Display wird aber nur "ist keine Primzahl" angezeigt. Wüsste jemand wie man dieses Promblem fixen könnte?

static void Main(string[] args) {    
    int zahl = 1;
        int zähler = 0;

        while (true)
        {
            for (int prüfer = 1; prüfer <= zahl; prüfer++)
            {
                if (zahl % prüfer == 0)
                {
                    zähler++;
                }

            }
            if (zähler == 2)
            {
                Console.WriteLine(zahl + " ist Primzahl");
            }
            else
            {
                Console.WriteLine(zahl + " ist keine Primzahl");
            }
            zahl++;

        }

    }

...zur Frage

Wie erstelle ich die while-schleife, wo alle geraden Zahlen von 2-20 miteinander addiert werden und "nur" die Endsumme ausgegeben wird?

Ich habe eine while-schleife erstellt, welche die geraden Zahlen von 2-20 miteinander addiert. So weit so gut. Mein Problem ist nur das Java auch die Zwischensummen ausgibt. Ich möchte allerdings nur die Endsumme 110 ausgegeben haben. Wie mache ich das?

int summe = 0;
int i = 2;
while (i<=20) {
    summe = summe + i;
    i=i+2;
    System.out.println(summe);

...zur Frage

Was möchtest Du wissen?

Deine Frage stellen