Доказательство Евклида, что существует бесконечное множество простых чисел, основано на методе reductio ad absurdum. Сначала Евклид предполагает, что верно противоположное: простых чисел существует лишь ограниченное множество. Однако, если это правда, одно из них должно быть самым большим простым числом. Обозначим самое большое простое число как P. Затем Евклид выводит новое простое число по следующему алгоритму: он перемножает все простые числа, начиная с 2 и до (включая) Р, и прибавляет к произведению единицу. Получается новое число

2 × 3 × 5 × 7 × 11 × … × P+ 1.

Согласно первоначальному предположению, это должно быть не простое, а составное число, поскольку оно, очевидно, больше Р, а мы решили, что Р – самое большое простое число. Следовательно, это число должно делиться по крайней мере на одно из существующих простых чисел. Однако из его конструкции следует, что если мы разделим его на любое простое число вплоть до (и включая) Р, получится остаток 1. А следовательно, если бы это число и в самом деле составное, оно должно делиться на какое-то простое число больше Р. Однако это предположение противоречит первоначальному утверждению, что Р – самое большое простое число, и мы, таким образом, доказали, что простых чисел бесконечно много.