Разложение целых чисел на простые множители.

Целые числа а и b называются взаимно простыми, если любой их общий делитель равен +1 или —1.

ПРЕДЛОЖЕНИЕ 1.2. Если целые числа взаимно простые, то существуют такие целые числа u, v, что

Доказательство. Рассмотрим множество

Легко видеть, что это множество не пусто и замкнуто относительно сложения и умножения на целые числа. Следовательно, есть идеал кольца целых чисел. Множество содержит число а, и число Множество содержит положительные числа, так как а и b взаимно простые и, значит, хотя бы одно из этих чисел отлично от нуля. Обозначим через d наименьшее положительное натуральное число, принадлежащее множеству I. Тогда согласно определению множества I существуют такие целые числа и, v, что По теореме 4.4.5, d есть общий делитель чисел а и b. Так как а и b взаимно простые и то отсюда следует, что Таким образом,

ТЕОРЕМА 1.3. Если произведение двух целых чисел делится на простое число , то по меныией мере один из сомножителей делится на .

Доказательство. Пусть произведение целых чисел делится на не делится на .

Тогда числа взаимно простые. Согласно предложению 1.2, существуют такие целые числа u, v, что , откуда

Так как делится на , то делится на , т. е. b делится на .

ТЕОРЕМА 1.4. Если произведение нескольких целых чисел делится на простое число , то по меньшей мере один из сомножителей делится на .

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

ТЕОРЕМА 1.5. Всякое целое положительное число, отличное от 1, представимо в виде произведения положительных простых чисел. Это представление единственно с точностью до порядка сомножителей.

Доказательство. Пусть а — целое положительное число, отличное от 1. Докажем представимость а в виде произведения положительных простых множителей, предполагая, что это утверждение верно для всех целых положительных чисел, не равных единице и меньших а. Если а — простое число, то утверждение верно. Если а — составное, то его можно представить в виде произведения целых чисел b, с, меньших а и больших единицы. Согласно индуктивному предположению, b и с представимы в виде произведения положительных простых чисел:

Подставив эти разложения в равенство получим представление числа а

в виде произведения положительных простых чисел.

Докажем единственность представления, используя метод индукции. Если а — простое число, то, очевидно, единственность представления следует из определения простого числа. Предположим, что единственность представления для всех чисел, меньших а, имеет место.

Предположим, что а составное, и рассмотрим два любых представления числа а в виде произведения положительных простых чисел:

Так как , то согласно теореме 1.4 по меньшей мере один из сомножителей делится на при соответствующей нумерации можно считать, что Поскольку — положительные простые числа, то Сокращая обе части равенства (1) на и полагая получим

Так как число меньше, чем а, то по индуктивному предположению число имеет единственное представление в виде произведения положительных простых чисел; следовательно, и при соответствующей нумерации Таким образом, число а единственным образом представимо в виде произведения положительных простых чисел.

СЛЕДСТВИЕ 1.6. Всякое целое число с, отличное от нуля и ± 1, единственным образом представимо в виде произведения

где — положительные простые числа и .

В представлении (1) могут встречаться равные простые числа. Если в представлении (1) объединить равные простые множители и изменить, если это необходимо, нумерацию, то представление (1) можно записать в виде

где — различные положительные простые числа, для Представление целого числа (отличного от нуля) в виде (2) называется его каноническим разложением на простые множители.