Пример 13. Доказать, что любое натуральное число, большее единицы, имеет простой делитель.

Рассматриваемое число делится на единицу и на само себя. Если других делителей нет, то оно простое, а значит, является искомым простым делителем. Если же есть и другие делители, то берём из этих других наименьший. Если бы он делился ещё на что-то, кроме единицы и самого себя, то это «что-то» было бы ещё меньшим делителем исходного числа, что невозможно.

Пример 14. Доказать, что для любых двух натуральных чисел существует наибольший общий делитель.

Поскольку мы договорились начинать натуральный ряд с единицы (а не с ноля), то все делители любого натурального числа не превосходят самого этого числа и, следовательно, образуют конечное множество. Для двух чисел множество их общих делителей (т. е. таких чисел, каждое из которых является делителем для обоих рассматриваемых чисел) тем более конечно. Найдя среди них наибольшее, получаем требуемое.

Пример 15. Доказать, что среди всех равных друг другу дробей непременно найдётся несократимая дробь.

Первое доказательство – со ссылкой на пример 14, а следовательно, с косвенным использованием принципа наибольшего числа. В нашем множестве дробей выберем произвольную дробь и найдём наибольший общий делитель d её числителя и знаменателя. Если d = 1, то выбранная нами дробь уже несократима. Если d ≠ 1, то сократим её числитель и знаменатель на это число d. Полученная дробь будет несократимой. Ведь если бы её можно было бы ещё сократить на какое-то число q, то произведение dq, большее числа d, было бы делителем числителя и знаменателя первоначальной дроби и d не было бы наибольшим общим делителем.