Файл: Чандрасекхаран, К. Введение в аналитическую теорию чисел.pdf

10 Га. I. Теорема единственности

ли. То же самое справедливо и в случае, когда q\—Р\ —

имеющих более одного канонического разложения.

§ 3. Второе доказательство теоремы 2. Доказатель­ ство основывается на решении в целых числах некото­ рых линейных уравнений. Введем некоторые новые по­ нятия.

Пусть а и b — целые числа, не равные одновременно нулю. Их наибольший общий делитель, который обозна­ чается через (а, Ь), определяется как наибольшее поло­ жительное целое число, которое делит одновременно а и Ь. Если (a, b) = 1, то мы будем говорить, что а и b — взаимно простые целые числа. Мы покажем, что если (a, b )= d , то уравнение ах-\-by=d разрешимо в целых числах х и у. Отсюда следует, что если р про­ стое и p\ab, то р\а или р\Ь. Из последнего факта в свою очередь вытекает теорема единственности разложения на простые сомножители.

называется модулем. Из определения следует, что если

ш, n ^ S , то

0 = т— m ^ S, —п = 0— n ^ S , т + п = т— (— n )e S .

Другими словами, если а е 5 , b^ S , то ax + by^ S при лю­ бых целых х и у. Если модуль состоит только из нуля, мы будем называть его тривиальным модулем. Нетриви­ альный модуль содержит, очевидно, бесконечно много положительных и отрицательных целых чисел. Мы мо­ жем сказать даже несколько больше:

Теорема 3. Каждый нетривиальный модуль S состоит

из всех целых кратных некоторого положительного це­ лого числа.

Доказательство. Так как S — нетривиальный мо­ дуль, он содержит некоторые положительные целые чис ла. Пусть d — наименьшее такое целое число. Тогда S содержит все целые кратные числа d. Для того чтобы

показать, что ими исчерпываются все элементы S, возь­ мем любое n ^ S . Мы можем представить п в виде п =

= dk + c, где k и с — целые и 0 ^Lc<cd. Так как d ^ S , то и dk^S. Далее, поскольку n e S , мы имеем п— dk^S, так что c^ S . Но c<id, a d — наименьшее положительное це­ лое в модуле 5. Следовательно, с = 0 и « есть целое крат­ ное числа d.

Отсюда мы получаем следующую теорему:

бой множество всех целых кратных числа d = (a , b).

Доказательство. Легко видеть, что множество S яв­ ляется модулем. Из теоремы 3 следует, что S есть мно­ жество всех целых кратных некоторого положительного числа е. Следовательно, е делит все элементы множест­ ва S; в частности, е|а и е\Ь. Так как d есть наибольший общий делитель чисел а и Ь, то e^.d. С другой стороны,

= d разрешимо в целых числах х и у. Другими словами,

наибольший общий делитель целых чисел а и b является их линейной комбинацией с целыми коэффициентами.

Следствие 2. Любой общий делитель целых чисел а

и b делит (а, Ь).

Из этих результатов теперь легко выводится

Теорема 6 (Евклид). Если а\Ьс и (a, b) = 1, то а\с.

Доказательство. Так как (a, b) = 1, то существу­ ют такие целые числа х и у, что ax-\-by= 1. Если мы ум­ ножим последнее равенство на с, то получим асх-\-Ьсу=

12 Г л. I. Теорема единственности

= с, и так как а\Ьс, то а\ (асх + Ьсу). Следовательно, а\с.

Г

Следствие. Если р — простое число и р |J”! ри где ка-

i=i

ждое ри i= \ , 2, г, также простое число, то р = р% по меньшей мере для одного i.

Мы можем теперь дать

Второе доказательство теоремы 2. Предположим, что целое число N имеет два различных канонических разложения

yv=p“ip“s---p“* = tf?1#

Тогда px\q\i q\* ■■■qfrH, следовательно, в силу следствия

теоремы 6 p\ — qi для некоторого t, Аналогично мы получаем, что каждое р равно некоторому q и каж­ дое q равно некоторому р. Таким образом, k= r и, так как оба разложения упорядочены по возрастанию сом­ ножителей, мы имеем

некоторого i, мы получили бы после деления на р?t равенство

в котором левая часть делится на ри а правая нет, что невозможно. Аналогично невозможен и случай a»<piСледовательно, a t= p i Для всех £, и потому каноническое разложение единственно.

§ 4. Наибольший общий делитель и наименьшее об­ щее кратное. С понятием наибольшего общего делите­ ля целых чисел а и Ь, данным в § 3, тесно связано по­ нятие наименьшего общего кратного.

Определение. Наименьшее общее кратное {а, b} двух целых чисел а и Ь, где аЬф 0, есть наименьшее положи­

§ 4. Наибольший общий делитель и наименьшее общее кратное 13

тельное целое число, которое делится одновременно на а

Для доказательства рассмотрим целое число р = ab/(a,b). Так как (а, b)\b, то р есть целое кратное а. Подоб­ ным же образом р есть целое кратное Ь. Тогда р будет общим кратным а и Ь. Пусть v — какое-либо другое об­ щее целое кратное а и Ь. Рассмотрим число

v v ■(а , ь)

р ab

Ho v/a и v/b являются целыми числами и, следовательно, v/p также будет целым числом. Таким образом, любое общее целое кратное чисел а и b есть целое кратное чис­ ла р. Значит, р будет их наименьшим общим кратным и

ab

{а,Ь}.

(а , ь)

Попутно мы показали, что наименьшее общее крат­ ное а и b делит любое общее кратное этих чисел.

Если а — положительное целое, то мы можем запи­ сать, что

а = П р“, « > 0 ,

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

Ь = Х\Р*, Р > 0 .

Легко видеть, что

§ 5. Последовательности Фарея. Если h я k — целые числа и А > 0, мы назовем hlk дробью с числителем h и

знаменателем k. Дробь hlk называется несократимой,

или сокращенной, если (h, k) = \. Дробь hlk называется

правильной, если Q^Zh/k^.\.

Последовательность Фарея порядка п, где п — поло­ жительное целое, — это последовательность Fn всех не­ сократимых правильных дробей hlk, у которых l^ k ^ ln , расположенных в неубывающем порядке. Например, F5 есть последовательность

Члены последовательности Фарея какого-либо поряд­ ка называются дробями Фарея. Заметим, что каждое ра­ циональное число m/п, такое, что O ^ m /n ^ l, равно не­ которой дроби Фарея.

Из теоремы единственности разложения на простые сомножители (теорема 2) следует, что несократимая дробь единственна. Другими словами, две равные меж­ ду собой несократимые дроби должны совпадать. Одна­ ко мы не хотим использовать теорему 2 и поэтому долж­ ны допустить возможность того, что две дроби Фарея могут быть равны между собой, но не совпадают. В этом случае мы упорядочим их по возрастанию числителей. Следующая теорема фактически исключает такую воз­ можность и подготавливает почву для третьего доказа­ тельства теоремы 2:

Теорема 7 (Фарей — Коши). Если Цт непосредствен­

но следует за hlk в последовательности Фарея FN, то kl—h m = 1.

Доказательство. Непосредственной проверкой мож­ но убедиться, что результат справедлив для FN при 1 г^ Л ^ б . Предположим, что результат справедлив для Fn, и докажем его для FN+X.

Пусть alb — несократимая правильная дробь, не принадлежащая FN. Тогда b ^ N -f l и дробь а/Ъ должна лежать между некоторыми двумя последовательными дробями hlk и IIm в последовательности Фарея FN,