Что такое простые числа и как они связаны с теоремой Евклида?

Простые числа — это натуральные числа больше единицы, которые делятся только на 1 и на самих себя 2. Например, это 5, 13, 29, 101, 1009 2.

Теорема Евклида утверждает, что для любого конечного списка простых чисел найдётся простое число, не вошедшее в этот список (то есть существует бесконечно много простых чисел) 34.

Доказательство Евклида: пусть дан конечный набор простых чисел 3. Нужно перемножить числа из этого набора и прибавить единицу 3. Полученное число не делится ни на одно число из данного набора, потому что остаток от деления на любое из них даёт единицу 3. Значит, число должно делиться на некоторое простое число, не включённое в этот набор 3.