А.И. Галочкин, Ю.В. Нестеренко, А.Б. Шидловский - Введение в теорию чисел (1159516), страница 4
Текст из файла (страница 4)
...,рх уже вычеркнуты, а по лемме 6 любое составное число п имеет простой делитель ч: 'уи. Итак, составление таблицы простых чисел, не превосходящих Ь', указанным процессом закончено, ьак только зачеркнуты все числа, кратные простым числам ~ )'Х. П р и м е р. К=40.
В приводимой ниже таблице подчеркнуты все числа, которые должны быть вычеркнуты в процессе применения решета Эратосфена. Иианпут йтэией Эиергп! вм. Н. й. ктавэтаав ! По индукции утверждение справедливо при любом и. Для того чтобы составить таблицу простых чисел, не пре, восходящих натурального числа Л~, имеется простой метод, который был известен еще древнегреческому математику Эратосфену. Этот метод называется решетом Эратосфена. Напишем одно за другим числа 2, 3, 4, 5, 6, 7, 8, 9, 1 О, 11, 12, 13, !4, !5, !6, 17, 18, !9, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40.
Числа 2, 3, 5, 7, 11, 13, !7, 19, 23, 29, 31, 37 составляют таб- .лицу простых чисел, не превосходящих 40. Решето Эратосфена — быстрый и удобный алгоритм для на- хождения всех простых чисел на отрезке от 1 до некоторого натурального числа Л~. В 1668 г. Д. Пелль (!6!Π†16) соста- вил таблицу простых чисел до 10:. С тех пор она много раз рас- ширялась. В 1914 г.
Д. Н. Лемер опубликовал таблицу про- стых чисел до 10'. Реализация решета Эратосфена при больших значениях Ж на ЭВМ встречается с трудностями, связанными с тем, что не- обходима большая машинная память для хранения всех чисел от 1 до У. Существуют модификации этого алгоритма, рабо- тающие столь же быстро, но использующие значительно мень- шую машинную память. Они выдают всю последовательность простых чисел в пределах от 1 до Ж отдельными отрезками. При существующих мощностях ЭВМ не составляет проблемы получить все простые числа до 10". Однако выписать все эти числа в таблицу сложно, так как их количество— 376079!2018 — очень велико.
В то же время с помощью некоторых алгоритмов найдены отдельные очень большие простые числа. Например, 2'"" — 1 244497 Таблицы простых чисел показывают, что простые числа встречаются все реже и реже с ростом их величины. Например, в первой сотне натуральных чисел — 25 простых чисел, во вто- рой — 21, в третьей — 16 н т. д. В первой тысяче — 168, во вто- ,рой — 135, в третьей — 120 и т.
д. Простые числа распределены в натуральном ряде весьма ,нерегулярно. Можно указать сколь угодно длинные отрезки натурально- го ряда, свободные от простых чисел. Так, при любом п числа Жь=2 ° 3 ° (и+1)+й. й=2, 3, ..., и+1, следуют одно за другим и все являются сос~авными, так как Ф(Хы й =2, ..., и+ 1. С другой стороны, существует много пар простых чисел вида р и р+2 с разностью, равной 2. Такие пары называют простыми числами-близнецами.
Среди них имеются очень боль- шие пары. До сих пор неизвестно, конечно или бесконечно мно- жество пар близнецов. В этом состоит знаменитая проблема близнецов. Приведем примеры близнецов: 3 и 5, 1! и 13, 17 и 19, 41 и 43, 10016957 и 10016959, 156 5ем +-1. В теории чисел разработаны методы, позволяющие изучать распределение простых чисел. зв Пусть х>0 — действительное число. Рассмотрим функцию п(х), выражающую число простых чисел (х. Ее можно записать следующим образом: п(х) =')" 1.
Рс» П р и м е р ы. и(!) =О, п(2) =1, п(10) =4, п(40) =12« и(!О") =376079120!8, п(р„) =и, если р„есть п-е простое число. Для функции л(х) нсизвестно никакой простой формулы,. которая позволяла бы изучать ее поведение. Важнейшей проблемой теории чисел является изучение асимптотического поведения функции п(х). Теорему Евклида можно сформулировать следующим образом: п(х)- +со при х — +ос, Установим вспомогательное предложение, с помощью которого будут доказаны двс теоремы о распределснии простых чисел. Обозначим (15) рм» Л е м м а 9. Р(х) >1пх и, следовательно, Р(х) -!-со при х — «+ со.
До к аз а тельство. При любом та=К имесм, что ', — ~~ ( ) ~ 1ь, 0<1<1. о=о о=о Полагая в этом неравенстве (=1/р, получаем неравенство 11-1 ! 1, . 1 1 — — ~ )1+ — + ... + —. р р1» 1 —— Р Отсюда при любом твнХ После перемножения скобок в правой части этого неравенства, %1 получим сумму вида ~,1 распространенную иа некоторые натуральные значения Ф. Если выбрать число я так, чтобы 2«' ы>х, то по основной теореме арифметики в эту сумму войдут все слагаемые, соответствующие значениям й от 1 до (х]„и еще какие-то слагае- 19 Р(х) > ~~)~ —.
((б) Пользуясь неравенством !п(1+г) <(, 0<(~1, при 1=1/К Й~1Ч, находим, что 1п (А + 1) — !п й =- !п (! + — ( < —, й = 1, 2, .... ь/ ь Складывая почленно последние неравенства при (!=1,...,п, получаем неравенство — ) 1п (и Р 1). ь р =-! Из неравенств (16) и (17) имеем Р(х) >1п((х)+1) >1и х, что доказывает утверждение леммы. Из того, что Р(х)- +со прн х- +со, следует новое доказательство бесконечности множества простых чисел. Оно было получено Эйлером. Рассмотрим сумму Я(х) =-- ~~~~ —, х > 2.
Р Р<» (17) Т е о р е м а 1. 5(х) >!п!их — 1/2, и поэтому ряд р расходится. Д о к а з а т е л ь с т в о. Пользуясь разложением функции (п(1+1), 0<1<1, в ряд Тейлора, получаем неравенство и и — (1и (1 — () + () = — + — + — + ... 2 3 4 и (р < — (1+(+(Р+ ...) = 2 2 (! — !) Полагая в этом неравенстве (=1(р и пользуясь равенством (15), имеем, что 1п Р (х) — о (х) = — ~~) ~ ( !п ( ! — ! ~ + — ) < ~~) Р р~с р~к — У ! ~1 ! ! <'Р 2р(р — !! Х ! 2н(л — Ц 2 Р~к Пра мые, соответствующие другим значениям и.
Отбрасывая последние слагаемые, будем иметь неравенство (р! Отсюда по лемме 9 находим, что 5(х)>!п1пх — !/2. Теорема доказана. Неравенство (17) можно получить другим способом с помощью нижеследующей леммы, которая окажется полезной в главах 2 и 3 для установления ряда других неравенств. Л е м м а 1О. Пусть т и а — натуральные числа, т>т. Функция 1(х) не возрастает на множестве т~хС+оо, Тогда вьтолняется неравенство п и-1 « « ) ~(х)Ых~~ ')" 1(я) ~«.1(т) + ) )(х)дх, а если сходится интеграл +и« ) 1(х) дх, то и неравенства ) )(х) дх~( ~, )(я) ~(~(т) + ) )(х)11х. Д о к а з а т е л ь с т в о. Ввиду монотонности функции 1(х) при любом й~т имеем, что 1(я+1) с1(х) с1(я), И~х ~И+1. Так как монотонная функция иитегрируема, то, интегрируя почленно эти неравенства на отрезке й-ах~у+1, получим ь+1 1(й+ 1) с ( 7(х)дх<Р(й).
Теперь, складывая левые из последних неравенств для значений й=т, т+1,...,а — 1, а правые из них для значений я=т, т+1, ..., и, находим неравенства « « «-1-1 « 1(/г)< ~~(х)дх, )и )(х)дх~( ~~," 1(й), Ь=г«+1 и« /П ь=ии из которых следует первое утверждение. Второе утверждение получается из первого переходом к пре.делу при п оо. Покажем, что плотность распределения простых чисел в натуральном ряде равна нулю. Теорема Эйлера.
п(х)/х-и.О, яри х- +оо. Рассуждения Эйлера не доказывали полностью этот резульигат. Строгое доказательство было дано А. Лежандром. 2! Докажем теорему Эйлера методом, основанным на идее решета Эратосфена. Пусть У(х, г) обозначает количество натуральных чисел и„ л~х, не делящихся ни на какое из г первых простых чисел рь ...,р, и У(х, О) — количество натуральных чисел, не превосходящих х.
Все числа и, а<х, не делящиеся на р„...,р„, разбиваются. на два класса: не делящиеся на р„и делящиеся на р„, Чисел первого класса будет Л'(х, г). Каждое число л из второго класса представляется в виде п=р,т, где т < — ", р,.Нт, 1=1, ...,г — 1. Р, Следовательно, второй класс содержит Ж ( —, г — 1) чисел,. ( Рю и справедливо равенство У (х, г — 1) = — У (х, г) + Ж ( —, г — 1) .
Я (х, «) =-- Л' (х, г — 1) — М ~ —, г — 1) . (18): ( Р« Отсюда При «=1 равенство (18) также справедливо. С помощью индукции и равенства (18) легко доказываем,. что +~Ч( — ',0) — ~,'У( ',0)+ с! сьь (19) Пусть $ удовлетворяет неравенствам 2<$<х, а г таково, что р„<5<р„.ы. Тогда я(х) <г+:Ч(х, г), (20) поскольку любое простое число либо равно одному из г первых простых чисел, либо содержится во множестве натуральных чисел, не делящихся ни на одно из этих простых чисел.
Подставим в правую часть неравенства (20) значение Л'(х, г) из равенства (19). Затем опустим у всех слагаемых зг где суммирование ведется по всем возможным сочетаниям и~ р„..., р, по одному, по два, по три и т. д. Так как Л'(х, О) =(х), то последнее равенство принимает вид.
знак целой части, заменяя этим целые части соответствующих чисел на сами числа. При такой замене каждого слагаемого допускается погрешность, меньшая единицы, а при замене всех слагаемых — погрешность, меньшая, чем 2', так как число всех слагаемых равно ~~~~ (т) =2'. т+2"<2'+'<2Ь1' и по лемме 9 Тогда ввиду неравенства :имеем, что л(х) < т+ 2' + х — ~~— Рт +~ —" — ~ " + Р~ Р) Р~Р1Рх с1 — — )<2 + —, 1 1 ь11 х Р 1п1 откуда и (") 22+1 — < — + —. х х ' !пав (21) л(х) =0( 1, х — +оо, ( 1и 1пх / 5 4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
