§ 3.6. Одно фундаментальное свойство простых чисел

Для доказательства единственности разложения целого числа в произведение простых нам понадобится следующее фундаментальное свойство простых чисел. Мы доказываем это свойство в настоящем параграфе, а § 3.7 и § 3.8 посвящены некоторым его приложениям. Начнем с леммы, которая послужит первым применением расширенного алгоритма Эвклида.

Лемма. Пусть натуральные числа, причем взаимно просты. Тогда:

(1) если произведение делится на то с делится на

(2) если с делится на а и на то с делится на

Докажем сначала утверждение (1). По предположению, числа a и b взаимно просты, Тогда результатом работы расширенного алгоритма Эвклида служат такие числа о и что

Перейдем теперь к «абракадабре» доказательства. Умножив обе части последнего равенства на с, получим

Ясно, что второе слагаемое в левой части делится на 6, но то же справедливо и для первого слагаемого. Действительно, оно делится на а поэтому, по предположению, и на Таким образом, вся сумма в левой части делится на 6, а поскольку она равна с, то первое утверждение доказано.

Выведем теперь (2) из утверждения (1). Раз с делится на а, то существует такое натуральное что Однако с делится и на и поэтому из (1) следует, что делится на 6, так как о и 6 взаимно просты. Значит, для некоторого целого к. Поэтому число

делится на об, что и утверждалось в

Эта лемма будет использоваться очень часто, начиная с доказательства следующего свойства простых чисел, которое сформулировано в виде предложения 30 книги VII эвклидовых «Начал». Это свойство настолько важное, что мы дадим ему имя. Будем называть его фундаментальным свойством простых чисел.

Фундаментальное свойство простых чисел. Если произведение натуральных чисел а делится на простое число то либо а делится на либо делится на

Фундаментальное свойство доказывается с помощью леммы. По предположению, делится на Если о делится на

то доказательство завершено. Предположим, что о не делится на Поскольку число простое, это означает, что Тогда из первого утверждения леммы вытекает делится на но взаимно просты), что делится на