Файл: Чандрасекхаран, К. Введение в аналитическую теорию чисел.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 29.10.2024
Просмотров: 68
Скачиваний: 0
§ 5. Последовательности Фарея |
15 |
скажем
k b m
где знак равенства допускается ввиду того, что единст венность несократимой дроби не предполагается. Опре делим целые числа Я и ц следующим образом:
X = ka—hb, р = Ы —am.
Тогда Я^О, и Я + ц > 0 , так как мы предположили, что теорема справедлива для последовательности FN, ко торой принадлежат дроби h/k и l/'m. Далее, по предпо ложению индукции kl—h m = 1, и тогда
Xl~Fph = kal—hain = a(kl—hm) — а.
Аналогично,
Xm + \x.k = b, |
(7) |
и поскольку (a, b) = 1, мы имеем (Я, ц) = 1. Таким обра зом, если h/ks^a/b^ll/m, (а, b) = 1, то
- Т = Г ± Г 1 ' к > 0 ’ Ц > 0 Д + ц > 0 , (Я ,ц)=1. |
|
b |
Km + [хй |
Обратно, если 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-\-\, и если
16 |
Г л. I. Теорема единственности |
(a /b )^ F N+1 , то b = N + 1. Далее, поскольку h/k и l/m яв
ляются последовательными членами в FN,
l + h Ф-F |
N ’ |
||
m + |
k |
||
|
|||
и потому m-\-k^N-\-1. |
Отсюда вытекает, |
что если Ь== |
|
— N + 1, |
то Х = 1 и р = 1 |
. Следовательно, |
|
а |
Fn + 1 => а = /г + /, b = k + m, — = h “t- l |
||
b |
|
b |
k-\-m |
и дробь alb, очевидно, удовлетворяет теореме относи тельно соседних дробей h/k и l/m, так как по предполо жению индукции для F n мы имеем kl—h m = 1. Таким образом, если теорема справедлива для FN, то она спра ведлива и для Fn+1 , и поскольку теорема справедлива
для F\, то она справедлива для всех Fn.
Из теоремы 7 следует, что несократимая дробь един ственна.
Определение. Дробь {h-\-l)l(k-\-m) называется
медиантой дробей h/k и l/m.
При доказательстве теоремы 7 мы показали неявным образом, что медианта двух дробей Фарея снова яв ляется дробью Фарея, а также доказали следующий ре зультат:
Теорема 8. Дроби, принадлежащие FN+U но не при надлежащие Fn, являются медиантами соседних дробей из Fn.
Из теоремы 7 вытекают также следующие утверж дения:
Теорема 9. Если h/k, h"/k", h'/k' — последовательные
дроби некоторой последовательности Фарея то h"/k"=
=(h + h ')/(k + k ').
Доказательство. По теореме 7 мы имеем kh"— hk"~
=1 и k"h'— h"k'= 1; вычитая одно равенство из другого, мы получаем требуемое утверждение.
Теорема 10. Если h/k и l/m — две последовательные дроби в последовательности Фарея FN, то k-\-m^N-\-1.
§ 6. Бесконечность множества простых чисел |
17 |
Доказательство. Так как |
|
|
Jl |
< |
< JL |
k |
k+ m |
m |
то медианта h/k и l/m не принадлежит F n■Следователь но, k-\-m>N.
Наконец, мы докажем следующую теорему:
Теорема 11. Если N > 1, то в Fn нет двух последова тельных дробей с одним и тем же знаменателем.
Доказательство. Пусть |
k > \ . |
Если h'/k |
непосредст |
|||
венно |
следует за |
h/k в FN, то h-\-l^.h'<Ck, |
и мы име |
|||
ли бы |
± |
< J L - < i ± i < ^ L |
|
|||
|
|
|||||
|
k |
^ k — l ^ |
k |
"" |
k |
|
Таким |
образом, |
h/(k— 1) |
будет |
лежать |
между h/k |
|
и h'/k в последовательности Fn, что противоречит наше му предположению о дробях h/k и h'/k.
Третье доказательство теоремы 2. Мы можем ис пользовать теперь наши знания о последовательностях Фарея для доказательства того, что уравнение ах-\-Ьу= = 1, где (а, 6) = 1, разрешимо в целых числах х, у. Как мы уже видели, отсюда следует справедливость теоре мы 2.
Так как утверждение очевидно, если ab = 0 или а = Ь , предположим, что Ь > а > 0 и (а, b) = 1. Рассмотрим дробь а/b. Мы можем считать ее членом некоторой по следовательности Фарея, например Ft,. Пусть дробь а/Ь непосредственно следует за h/k в этой последовательно сти. Тогда по теореме 7 имеем ka—hb— 1, так что x — k и г/= —h дают решение уравнения ax+ by= 1.
§ 6. Бесконечность множества простых чисел. Мы получили три различных доказательства теоремы един ственности разложения на простые сомножители. Дока жем теперь, что простых чисел бесконечно много.
Теорема 12 (Евклид). Существует бесконечно много простых чисел.
2— 870
18 |
Г л. I. Теорема единственности |
|
Мы дадим два различных доказательства этой тео ремы. Первое доказательство принадлежит Евклиду, а второе— Г. Пойа. Третье доказательство, принадле жащее Эйлеру, будет дано в гл. 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. В самом деле, предположим, что
Pi < 2 , р2< |
22, р3 < 2 \ . .. , р я < 2 * в- |
1. |
|
Тогда |
|
|
|
Рп-л " РгРг-Рп |
1 < 2 1-1-2+Ч---- \~2п—1 |
1 |
< 2 2 , |
и мы получаем требуемый результат с |
помощью ин |
||
дукции. |
|
|
|
Доказательство Пойа теоремы 12 использует свой ства чисел Ферма. Число Ферма /„ есть целое число вида
|
§ 6. Бесконечность множества простых чисел |
19 |
fn= |
22” + l. п ^ \ . Мы покажем, что теорема |
12 являет |
ся |
следствием следующей теоремы: |
|
Теорема 13. (Пойа). Любые два различных числа Фер ма взаимно просты.
Доказательство. Пусть fn и fn+ h{k> 0) — два любых числа Ферма. Предположим, что m — такое положитель
ное целое число, что m\fn и m\fn+h. Полагая х — 2?п, мы получаем
fn + k ~ 2 _ х 2>г — 1
fn |
Х + 1 |
так что fn\(f„+h—2). Отсюда следует, что т| (/„+&—2), и так как m\fn+k, то m |2. Но числа Ферма нечетны. Сле довательно, т = 1 и доказательство теоремы 13 закоп чено.
Второе доказательство теоремы 12 (Пойа). Из теоре мы 13 следует, что каждое из чисел Ферма fь f2, ..., fn Де лится на нечетное простое число, которое не делит лю бое другое число Ферма. Следовательно, имеется по меньшей мере п нечетных простых чисел, не превосходя щих fn- Следовательно, простых чисел бесконечно много.
Далее, если мы рассмотрим f0= 3 при п = 0, то, по скольку рi = 2 и поскольку имеется по меньшей мере п нечетных простых чисел, не превосходящих fn для п ^ 1 , мы получим, что pn+2 ^ fn , где рп означает n-е простое.
Тогда
причем эта оценка лучше полученной ранее. Ферма заметил, что числа
fi = 5, fa= 17, f3 = 257, Д = 65537
являются простыми, и предположил, что все /п также являются простыми. Однако это предположение было опровергнуто Эйлером, который показал, что f5 делится на 641. Простое доказательство последнего факта, пред ложенное Г. Т. Беннетом, сводится к следующему:
f&= 226 + 1 = 232 + 1 = (2-27)4 + 1.
2*