Научная библиотека

6. Простые числа.

Целое положительное число, большее единицы, называется простым, если оно не имеет целых положительных делителей кроме себя и единицы. Так, числа 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 простые, а числа 4, 6, 8, 9, 10, 12, 14, ... нет. Непростые числа 4, 6, ... называются также составными. Число 1 не относится ни к простым, ни к составным числам.

Предложение 12. Всякое целое число, большее 1, делится по крайней мере на одно простое число.

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

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

- Простых чисел существует бесконечно много. Это непосредственно вытекает из следующего предложения.

Предложение 13. Каково бы ни было конечное множество простых чисел всегда найдется простое число, не принадлежащее этому множеству.

Доказательство. Рассмотрим число . В силу предложения 12 оно делится по крайней мере на одно простое число . Это число не может совпадать ни с одним из чисел . Действительно, если то 1 делится на как разность двух чисел, делящихся на что невозможно.

Это рассуждение было известно еще Евклиду.

Предложение 14. Если целое число не делится на простое число , то и взаимно просты.

Доказательство. Пусть . Так как делится на d и простое, для d имеются только две возможности: или . В первом случае делится на , во втором пир взаимно просты, что и требовалось доказать.

Из предложения 14 вытекает следующее утверждение.

Предложение 15. Если два различных простых числа, то они взаимно просты.

Действительно, меньшее из них не делится на большее, и, следовательно, они взаимно просты.

Предложение 16. Если произведение двух целых чисел делится на простое число, то по крайней мере один из сомножителей делится на это простое число.

Действительно, пусть делится на , где простое. Если а делится на , то предложение справедливо. Если а не делится на , то а и взаимно просты, а тогда, согласно предложению 10, b делится на .

Это предложение легко обобщается.

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

Доказательство. Применим метод математической индукции по числу сомножителей. База есть предложение верно для двух сомножителей. Допустим, что оно верно для произведения сомножителей. Пусть теперь делится на простое число . Так как заключаем на основании предложения 14, что либо делится на р, либо произведение делится на . Во втором случае, в силу индуктивного предположения, один из сомножителей делится на , а в первом делится на . Тем самым предложение доказано.

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

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

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

Допустим, что теорема верна для всех натуральных чисел, меньших и в этом предположении докажем ее для числа .

В силу предложения 12 число делится на некоторое простое число так что причем Если то есть «произведение» одного сомножителя Если то в силу индуктивного предположения допускает разложение на простые сомножители: и тогда Возможность разложения доказана.

Докажем однозначность разложения с точностью до порядка следования сомножителей. Пусть где все числа простые. Из этого равенства следует, что произведение делится на . В силу предложения 15 один из сомножителей должен делиться на и в силу простоты q совпадать с Без нарушения общности, за счет изменения нумерации сомножителей второго разложения, мы можем принять, что так что откуда . Но . Поэтому можно применить индуктивное предположение, так что и простые числа отличаются от только порядком следования. Теорема доказана.

Среди сомножителей в разложении могут быть равные. Их принято объединять в виде степеней. Разложение в форме при попарно различных называется каноническим разложением натурального числа . Каноническое разложение распространяется на все целые числа, кроме 0, в форме

где принимает значения 0, 1.

Далее, каноническое разложение может быть распространено на дробные рациональные числа, если допустить отрицательные значения для Чтобы получить каноническое разложение для дробного рационального числа, нужно написать разложения для числителя и знаменателя и выполнить деление одного на другое, употребляя, в случае надобности, отрицательные показатели. Так,

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