2. Применение к основной теореме арифметики

Тот факт, что d = (а, b) всегда может быть записано в форме d = ka + lb, позволит нам привести доказательство основной теоремы арифметики, отличное от того, которое было изложено на стр. 47. Сначала в качестве леммы мы докажем следствие, приведенное на стр. 48, а затем уже из него выведем теорему. Таким образом, ход мыслей будет теперь противоположен прежнему.

Лемма. Если произведение ab делится на простое число р, то или а, или b делится на р.

Предположим, что а не делится на р; тогда (а, р) = 1, так как р имеет лишь два делителя: р и 1. В таком случае можно найти такие целые числа k и l, что

Умножая обе части равенства на b, получим:

Так как ab делится на р, то можно написать

так что

и отсюда ясно, что b делится на р. Таким образом, мы установили, что если ab делится на р, но а не делится, то b непременно делится на р; значит, во всяком случае, или а, или b делится на р, раз ab делится на р.

Обобщение на случай произведения трех или большего числа множителей не представляет труда. Например, если abc делится на р, то достаточно дважды применить лемму, чтобы получить заключение, что по меньшей мере один из трех множителей а, b и с делится на р. В самом деле, если р не делит ни а, ни b, ни с, то не делит ab и, следовательно, не делит (ab) с = abc.

Упражнение. Обобщение этого рассуждения на случай произведения из произвольного числа n множителей требует явного или неявного применения принципа математической индукции Воспроизведите все детали соответствующих рассуждений.

Из полученного результата немедленно получается основная теорема арифметики. Предположим, что имеется два разложения целого числа N на простые множители:

Так как р₁ делит левую часть равенства, то должно делить и правую и, значит (см. предыдущее упражнение), должно делить один из множителей q_k. Но q_k - простое число; значит, р₁ должно равняться q_k. Сократив равенство на общий множитель р₁ = q_k, обратимся к множителю р₂ и установим таким же образом, что он равен некоторому q_t. Сократив на р₂ = q_t, переходим, далее, к множителю р₃ и т. д. В конце концов сократятся все множители р, и слева останется 1. Так как q - целые положительные числа, то и справа не может остаться ничего, кроме 1. Итак, числа р и числа q будут попарно равны, независимо от порядка; значит, оба разложения тождественны.