Лекции по алгебре - Фаддеев Д.К.
Скачать (прямая ссылка):
Предложение 13. Каково бы ни было конечное множество простых чисел {pi,p2, Pk}, всегда найдется простое число, не принйдЛежащее этому множеству.
U
ЦЕЛЫЕ ЧИСЛА
1ГЛ I
Доказательство. Рассмотрим число л == pip2 ... р* + I. В силу предложения 12 оно делится по крайней мере на одно простое число р. Это число р не может совпадать ни с одним из чисел Рь Р2, Pk- Действительно, если р — pi, то 1 делится на pi как разность двух чисел, делящихся на р,, что невозможно.
Это рассуждение было известно еще Евклиду.
Предложен-ие 14. Если целое число п не делится на простое число р, то п и р взаимно просты.
Доказательство. Пусть d = (n, р). Так как р делится на d и р простое, для d имеются только две возможности: d = р или d~ 1. В первом случае п делится на р, во втором п м р взаимно просты, что и требовалось доказать.
Из предложения 14 вытекает следующее утверждение.
Предложение 15. Если р\ и р2— два различных простых числа, то они взаимно просты.
Действительно, меньшее из них не делится на большее, и, следовательно, они взаимно просты.
Предложение 16. Если произведение двух целых чисел делится на простое число, то по крайней мере один из сомножителей делится на это простое число.
Действительно, пусть ab делится на р, где a, & eZ, р — простое. Если а делится на р, то предложение справедливо. Если а не делится на р, то а и р взаимно просты, а тогда, согласно предложению 10, Ъ делится на р.
Это предложение легко обобщается.
Предложение 17. Если произведение нескольких целых чисел делится на простое число, то на него делится хотя бы един из сомножителей.
Доказательство. Применим метод математической индукции по числу сомножителей. База есть —предложение верно для двух сомножителей. Допустим, что оно верно для произведения k—1 сомножителей. Пусть теперь 0)02 ... ak делится на простое число р. Так как aia2 ... ak = a\(a2 ... ak), заключаем на основании предложения 14, что либо а\ делится на р, либо произведение а2 ... ак делится на р. Во втором случае, в силу индуктивного предположения, один из сомножителей а2, ..., ак делится на р, а в первом ai делится на р. Тем самым предложение доказано.
Теперь мы в состоянии доказать основную теорему теории делимости целых чисел.
Теорема 18. Каждое натуральное число, большее единицы, может быть представлено в виде произведения простых сомножителей, и два таких разложения могут отличаться только порядком следования сомножителей.
Доказательство. Применим метод индукции. Для числа 2 утверждение теоремы тривиально (так же, как и для всякого простого числа). Допустим, что теорема верна для всех натуральных
S 2)
ТЕОРИЯ СРАВНЕНИИ
15
чисел, меньших п, и в этом предположении докажем ее для числа п.
В силу предложения 12 число п делится на некоторое простое число pi, так что п. =» р\П\, причем ni < п. Если п\ = 1, то п есть «произведение» одного сомножителя P1. Если п\ > 1, то в силу индуктивного предположения п\ допускает разложение на простые сомножители: nt = рг ... рк, и тогда п = РіРг ... рк. Возможность разложения доказана.
Докажем однозначность разложения с точностью до порядка следования сомножителей. Пусть п = р\р2 ... рк = qiq2 ... qi, где все числа р\, р2, Pk, qx, <7г.....<7/ простые. Из этого равенства следует, что произведение <7і<?2 .-Ці делится на р\. В силу предложения 15 один из сомножителей <7i, q2, qi должен делиться на pi и в силу простоты qi, q2, qi совпадать с р{. Без нарушения общности, за счет изменения нумерации сомножителей второго разложения, мы можем принять, что qi = pi, так что pip2 ... Pk = РФ ••¦ <7<, откуда р2...рк = q2...qi. Но р2 ... рк = = n/pi < п. Поэтому можно применить индуктивное предположение, так что I = k, и простые числа q2, ..., qk отличаются от р2, ..., рк только порядком следования. Теорема доказана.
Среди сомножителей в разложении п = pip2 ... р* могут быть равные. Их принято объединять в виде степеней. Разложение в форме tt = p<Jip?2 ... рат при попарно различных pi, р2, рт
называется каноническим разложением натурального числа п. Каноническое разложение распространяется на все целые числа, кроме 0, в форме
П = ( — l)aopaipa2 : . . p«m, 1 2 m
где ссо принимает значения 0, 1.
Далее, каноническое разложение может быть распространено на дробные рациональные числа, если допустить отрицательные значения для аь ат. Чтобы получить каноническое разложение для дробного рационального числа, нужно написать разложения для числителя и знаменателя и выполнить деление одного на другое, употребляя, в случае надобности, отрицательные показатели. Так, -^- = 2-^5-1?, -^- = (-1)2^3-?3.
Теорема об однозначном разложении целых чисел на простые множители играет исключительно большую роль в теории чисел.
§ 2. Теория сравнений
Пусть т — данное натуральное число. Все целые числа по отношению к числу т естественно разбиваются на т классов, если отнести к одному классу числа, дающие один и тот же остаток ПРИ Делении на т. Так, если т — 2, целые числа разбиваются на
16
