Апология математики (сборник статей)

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

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

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

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

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

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

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

Третье доказательство – с использованием второй формулировки принципа наименьшего числа. Предположим, что в нашем множестве дробей нет несократимой. Возьмём произвольную дробь из этого множества и сократим её. Полученную тоже сократим и т. д. Знаменатели этих дробей будут всё меньшими и меньшими, и возникнет бесконечная убывающая последовательность натуральных чисел, что невозможно.