книги из ГПНТБ / Чандрасекхаран, К. Введение в аналитическую теорию чисел

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,

скажем

k b m

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

X = ka—hb, р = Ы —am.

Тогда Я^О, и Я + ц > 0 , так как мы предположили, что теорема справедлива для последовательности FN, ко­ торой принадлежат дроби h/k и l/'m. Далее, по предпо­ ложению индукции kl—h m = 1, и тогда

Xl~Fph = kal—hain = a(kl—hm) — а.

Аналогично,

и поскольку (a, b) = 1, мы имеем (Я, ц) = 1. Таким обра­ зом, если h/ks^a/b^ll/m, (а, b) = 1, то

Обратно, если X и р, — целые числа, такие, что Я^О,

ц5&0, Я+|-1>0, (Я, ц) = 1, и мы определим а и b равен­ ствами а= Я /+ р /г, b — Xm-\-\ik, то однозначно X— = к а —hb, ц — Ы— am и (a, b) = 1, так что дробь ajb не­ сократима. Кроме того, из равенства kl—h m = 1 следует, что h/k^.a/b^.l/m . Таким образом, а/b принадлежит FyI для некоторого М.

Так как k > 0 , m > О, (Я, ц) = 1, то мы видим также, что b^m-\-k только в трех случаях Я, р= 0, 1; 1, 1; 1, О, которые приводят соответственно к значениям а, Ь —

— h, k; l+h, m + k\ /, m. Далее, Я=т^0. Действительно, ес­ ли бы Я = 0 , то дробь а/Ь = (ц/г)/ (ц/г) не была бы несо­ кратимой, за исключением случая р = 1 . В последнем же случае, согласно равенству (7), мы имели бы b = k , что противоречит предположению о том, что b^N-\-1>& . Подобным же образом р=£0. Сле'довательно, b^m-\-k, только если Я = р = 1 . Мы имеем b^N-\-\, и если

Мы дадим два различных доказательства этой тео­ ремы. Первое доказательство принадлежит Евклиду, а второе— Г. Пойа. Третье доказательство, принадле­ жащее Эйлеру, будет дано в гл. VII, § 1.

Первое доказательство теоремы 12 (Евклид). Допу­ стим, что 2, 3, 5,..., р— множество всех простых чисел и р— наибольшее из них. Рассмотрим целое число

<7— (2-3-5.../?) + 1-

Это число не делится ни на одно простое до р включи­ тельно. Но <7>1 и тогда q или само простое, большее р, или оно делится на простое число, большее р. В обоих случаях существует простое, большее р. Следовательно, простых чисел бесконечно много.

Если через рп мы обозначим n-е простое число, то из сказанного следует, что

П

Pm\Y[ Pi + 1

(=1

для некоторого т > п . Следовательно, pn+i^Pm ^

П

< F [P i+ К /> "+ 1 п р и я > 1. i=i

На самом деле с помощью подобных рассуждений мы можем доказать несколько больше, а именно что

Р „ < 2 " " -1> я > 1,

причем рп< .22”-1 при я > 1. В самом деле, предположим, что

Доказательство Пойа теоремы 12 использует свой­ ства чисел Ферма. Число Ферма /„ есть целое число вида