Wir starten mit der Annahme, dass es endlich viele Primzahlen gibt. Also gibt es auch eine größte, nennen wir sie 'n'. Nun multiplizieren wir alle Primzahlen bis einschließlich n miteinander und erhalten so deren kleinstes gemeinsames Vielfaches, 'v'. Nun addieren wir +1 dazu. Dadurch erhalten wir eine neue Zahl, v+1.
Wie du schon richtig festgestellt hast, kann v+1 keine der bekannten Primzahlen sein, weil v+1 ja viel größer ist als jene. Daher gibt es zwei Möglichkeiten:

1. v+1 ist keine neue Primzahl und muss somit eine eindeutige Primfaktorenzerlegung besitzen, das heißt, durch mindestens eine der uns bekannten Primzahlen teilbar sein.
2. v+1 ist eine neue Primzahl, die wir noch nicht gekannt haben.
   Wenn aber 1) zutrifft, also, dass v+1 durch eine der uns bekannten Primzahlen teilbar ist, dann ist diese sowohl ein Teiler von v als auch von v+1. Die einzige Zahl, die sowohl v als auch v+1 teilt, ist aber 1 und 1 ist keine Primzahl. Daher wissen wir, dass 1) nicht zutrifft und 2) gilt, v+1 also eine neue Primzahl ist, die wir noch nicht gekannt haben.
   (Bsp.: Wir kennen die Primzahlen 2, 3 und 5 und glauben das sind alle. Dann ist 2 * 3 * 5 + 1 = 31. Wir wollen eine Primfaktorenzerlegung von 31 bestimmen, um 1) zu zeigen. Aber 31:2 = 15 plus Rest 1, 31:3=10 plus Rest 1, 31:5 = 6 plus Rest 1. 31 lässt sich also nicht in Primfaktoren zerlegen. Folglich ist 31 eine Primzahl, die wir noch nicht gekannt haben.)