Пример (для самостоятельного решения)

Составить таблицу простых чисел не превосходящих N =60.

Единственность разложения на простые сомножители

Теорема.

Всякое целое a или взаимно просто с данным простым p, или же делится на p.

Доказательство.

(a, p) будучи делителем p может быть равно или 1 или p. В первом случае a взаимно просто с p, во втором a делится на p.

Теорема.

Если произведение нескольких сомножителей делится на простое p, то по крайней мере один из сомножителей делится на p.

Доказательство.

Каждый сомножитель или взаимно прост с p или же делится на p. Если бы все сомножители были взаимно просты с p, то их произведение было взаимно просто с p. Поэтому, хоть один сомножитель делится на p.

Теорема.

Всякое целое, большее единицы, разлагается на произведение простых сомножителей и притом единственным образом (если отвлечься от порядка следования сомножителей).