An erster Stelle im BUCH steht der Satz, dass es unendlich viele Primzahlen gibt - und es werden gleich sechs Beweise dafür angeführt. Primzahlen sind Zahlen, die nur durch sich selbst und durch 1 teilbar sind, zum Beispiel 5, 7, 47 oder 101. Der berühmteste und älteste Beweis für deren Unendlichkeit stammt von Euklid und ist mehr als 2200 Jahre alt. Es ist ein Widerspruchsbeweis: Euklid ging von der Annahme aus, es gebe nur endlich viele Primzahlen, und zog daraus so lange logische Schlüsse, bis er auf einen offensichtlichen Widerspruch stieß. Damit musste irgendetwas falsch sein. Da sich in die Schlusskette kein Lapsus eingeschlichen hatte, konnte es nur die Annahme sein. Demnach musste es unendlich viele Primzahlen geben.

Der Beweis im Detail: Angenommen, es existierten nur endlich viele Primzahlen. Dann ließen sich diese auflisten, etwa als p1, p2, p3, ... pr, wobei r für die (endliche) Anzahl der Primzahlen steht. Nun betrachtete Euklid die Summe aus dem Produkt dieser Zahlen plus 1: p1 * p2 ... * pr + 1. Diese Zahl, sie möge n heißen, kann keine Primzahl sein, weil sie in der vollständigen Primzahl-Liste p1, ... pr nicht auftaucht. Also muss sie durch eine Primzahl teilbar sein, irgendein pi, mit i zwischen 1 und r. Dieses pi ist natürlich auch ein Teiler des Produkts p1 * ... * pr, also der Zahl n-1. Wenn pi ein Teiler von n und n-1 ist, dann muss es auch die Differenz teilen. Die ist aber 1, und das ist unmöglich. Unsere Annahme muss demnach falsch gewesen sein. Also gibt es unendlich viele Primzahlen.

William Dunham, Mathematikprofessor im amerikanischen Pennsylvania, bezeichnet Euklids Beweis als Lackmustest für mathematische Sensibilität: "Diejenigen mit einem natürlichen Hang zur Mathematik rührt er zu Tränen, diejenigen ohne einen solchen Hang finden ihn zum Heulen." Für Erdös stellte er ein Schlüsselerlebnis dar: "Als ich zehn war, erzählte mir mein Vater vom Euklidischen Beweis, und ich hatte angebissen."