AOP_Tom2 (1021737), страница 203
Текст из файла (страница 203)
Впервые эта теорема была строго доказана фон Мангольдтом (гоп Мапба!кЬ) [Сге/- /е 114 (1895), 255-305), который на самом деле показал, что остаточный член 0(1) равен С+ / к///'((/~ — 1)/1п/) минус 1/'2Ь при условии, что число и равно /к-й степени простого числа. Постоянная С равна 1! 2 — 1и 2 = "К -!-!и !и 2+ 2„„> (!и 2)ч/ии! = О 35201 65995 5754747542 735676773643656 84471+. [Итоги исследований этой задачи за 100 лет., прошедших пакле публикации работы фон Мангольдта, подвел А.
Л. Карацуба (А. А Кагашнба) в книге Сотр/ех Апа/учбз т ччикпбег ТЬеогу (СКС Ргтэ, 1995). В книге Эрика Баха (Епс ВасЬ) и Джеффри /Пзллита (бе//геу 8Ьа!!!!) А/бог/Мпп/к! /Ч/нтбег ТЬеогу 1 (М1Т Ргет, 1996), глава 8, проанализирована связь гипотезы Римана с конкретными задачами теории чисел.) 26.
Если число Ак не являетсн простым, то оно содержит простой множитель д < ~(кХ. Согласно условиям задачи каждый простой делитель р числа / содержит целое числа хр, такое, что порядок числа хр по модулю д является делителем числа 87 — 1, но не (Л» — 1)/р. Поэтому, если число рь делит /, порядок числа хр по модулю»й будет кратным р". В упр.
3.2.1.2-15 показано, что существует элемент х порядка / по модулю д. Однако это невозможно, поскольку тогда должно быть д~ > (/+ 1) > (/+ 1)г >»"р, и равенство не может быть выполнено [Ргос. СашЬ. РЛИ. Яос. 18 (1914), 29-30.[ 27. Если число Л не делится на 3 и если Л < 2" + 1, то число Л 2" + 1 будет простым тогда и 2" только тогда, когда З~ " ся — 1 (по модулю Л 2" + Ц (согласно упр. 26).
Если же йг2" +1— простое число, то согласно закону взаимности квадратичных вычетов чиг ю 3 не является квадратичным вычетом по модулю Л 2" + 1, поскольку (Л 2" + 1) »под 12 = 5. (Этот способ проверки был предложен без доказательства Протом (РгойЬ) в Сошрйез Веп»1пэ Асад. Ясй. Рапи 87 (1878), 926.) Чтобы применять способ проверки Прота с достаточной эффективностью, необходимо обеспечить вычисление значения х пюд(Л 2" + 1) с почти такой же скоростью, как и вычисление значения х~гпод(2" — 1), Положим, что хэ = А 2" + В; тогда хз ря  — [А/Л) + 2" (А шод5), и в случае, если Л представляется с однократной точностью, остаток вычисляется легко.
[Несколько сложнее проверить»прастотур чисел вида 3 2" + 1; для этого необходимо сначала прииенить случайные числа однократной точности, пока одно из них в соответствии с законом квадратичной взаимности не окажется квадратичным без остатка пзод 3 2" + 1. После этага в способе проверки, описанном выше, заменяем»3» этим числом. Если окажется, что ппюд4 ф О, можно использовать число 5. Получается, что число 3 2" + 1 будет простым, когда и = 1,2,5,6,8, 12, 18, 30.
36,41, 66, 189, 201,209,276,353,408, 438, 534, 2208, 2816, 3168, 3189, 3912, 20909, 34350, 42294, .42665, 4468а, 48150, 55182, 59 973. 80190, 157169, 213 321; других таких чисел вплоть до п < 300 000 нет. Число 5 2" + 1 будет простым, когда и = 1,3,7,13,15,25.39,55,75. 85,127,1947,3313,4687,5947, 13165, 23473,26607, 125413, 209787,.240937 (и < 300000), См. К. М. 11оЬ1пэоп, Ргос. Атег. МайЛ. Яос. 9 (1958)., 673-681; С. р'. Соппасйй, Н.
С 1%111ап»э, МайЛ. Сошр. 35 (1980), 1419-1421; Н. ПоЬпег, %. Кейег, Маййь Сотр. 64 (1995), 397-405; 3. Я. Уоипй, МайЛ. Сотр. 67 (1998), 1735 †17 ) 28. 14. еем /(р,рэб) = 2/(р + 1) + /(р,б)/р, поскольку 1/(р + 1) †вероятнос того, что число А кратно числу р; если б шод р ф О, то /(р, рд) = 1/(р + 1).
Так как .4 — (41» + З)В не может быть кратно 4. то /(2, 45+3) = -'. Так как Аэ — (ЗЛ+ 5) В не может быть кратно 8, та/(2 85+5) = з. /(2, 88+1) = -'+-'+-'+~1+ —,' + = ». Если д»Р '1»~ шодР = (1, Р— 1), то соответственно для нечетных р получим /(р, б) = (2р/(Р 1) ~ О) 29. Количество неотрицательных целых решений х, неравенства х~+ +х <» равно ( ~") > т"/г!; каждое из этих решений соответствует единственному целоиу числу р,'...р» < и.
[Более точнме оценки для специального случая, когда числа р, являются Зчми простыми числами при всех /Ь приведены в работах 7». С. де Вгвй)п., 1пдаб. МайЛ. 28 (1966), 240 — 247; Н. На!Ьегжаш, Ргос. Лопбоп МайЛ. Бос. (3) 21 (1970), 102-107.] 30. еслир",...р'„, шхй (па модулю ч), можно найти такие ро что р",' .. р», ш(лю) (по модулю а, '); поэтому согласно китайской теореме,об остатках находим 2" значений величины Х, таких, что Х»э р",...р' (по модулю 1»»).
Количество пар (е„,е', е,', ...е„',), для которых соблюдаются указанные свойства и которым соответствуют такие последовательности (еп.,.,е ), не превышает величины (,," ). Теперь для каждого из 2" двоичных чисел а = (оп .. аз)й положим, что п, — количество показателей (еь..., е' ), таких, что (р,'... р'„Г)йи '1»»я (-1) * (по модулю 9,). Следовательно, доказано, что требуемое количество целых чисел Х не меньше 2~(2 пэ)/[ ' ) Поскольку 2,, и„- .количество способов замены путем перестановок не более г/2 объектов из множества т обьектов, т.
е. (,+ей ), получаем 2', и, > ( рй )э/2 > т"/(2»(г/2)Р). [Дополнительные сведения, касающиеся тонкостей применения теоремы П, приведены Шнорром в Х А!8огййшэ 3 (1982)р 101-127,) 31. Чтобы показать, что Рг(Х < 2т) < е Т~, присвоим п = М, рМ = 4т и РМ = 2пь фт-; 32. Пусть ЛХ = (ТТ)т) и пусть все х) каждого из сообщений ограничены интервалом 0 < х < ЛХф — ЛХ . Если х > ЛХ, кодируем его в виде хз п)ос! 7)), как и ранее, ио при х < м нзлтеняелт кодировштие на (х+рлх) пюб тт, где у- — случайное число, принадлежащее з интервалу Мз — М < у < МР. При декодировании сначала вычисляем кубический корень и, если в результате получаем значение М вЂ” ЛХ или большее, берем остаток п)от! М.
З Р 34. Пусть Р— веронтность того, что выпачняется равенство х )по)1р = 1; пусть также Т,) — вероятность того, что выполняется равенство х шо)! д = 1. Вероятность того, что бст!(х — 1, Лт) = р или 9, равна Р(1 — Т )) + 1;)(! — Р) = Р + Те — 2Р!е. Если Р < -' нли 1;) < -', данная вероятность > 2(10 е — 10 'з), поэтому есть хорошие )пансы найти простой множитель после выполнения примерно 10 1об рп арифметических операций по модулю У, С друтой стороны, если Р > - и Т;) > —, то Р ш С'„Т вЂ” 1, поскольку есть основная формула 1 1 Р = бстЦш, р — 1)/р; поэтому в подобном гзучае т крмтна !сш(р — 1, 9 — 1).
Полтаким, что пт = 2"г, где г нечетно, и построим последовательность х' пии1 Лт, хз" шот! )Р), ..., хэ "шот! 71)) так же, как и в результате выполнения алгоритма Р, получаем, что впервые 1 появится после значения р, не равного !Т) — 1, с вероятностью, не меньшей -'; следовательно, боб(р — 1, ЛХ) = р илн ф Зб. Пусть / = (рр ' — дм ') п)от! Л), Поскольку р прот!4 = 9щод 4 = 3, то (=') = (=') = ') (с) = -(с) = — 1 и, кроме того, (1) = — (з) = — 1. Пусть для данного сообщения х в Р Р м Р интервале 0 < х < -'(ЛХ вЂ” Ъ) имеем й = 4х + 2 или 8х + 4, любое из которых удовлетворяет условию (Ц = 1. Тогда передаем сообщение й' шот! )9.
Чтобы закодировать это сообщение, сначала используем Б)211Т-блок для нахождения едвнственного числа рр такого, чтобы выполнялись условия рз ш йз шот! Лт и (и) = 1 )Р и 9 было четным. Тогда имеем у = й, поскольку три остальных квадратных корня из числа У равны Л) — й и (х/х) шот)ЛТ: первый из этих корней нечетнь)й, два других имеют отрицательные символы Якоби. Декодирование на этом завершается присвоением х ф- (у/4), если у п)о)! 4 = 2, и х Р- (у/8) — в противном случае. Каждый, кто сможет декодировать такое закодированное сообщение, смоясет найти множители числа Л), поскольку декодирование ложного сообщения х шот! !Т) в случае, когда ( лг ) = -1, позволяет обнаружить (х/) шот! Ю и ((х/) шот! Л)) — 1 имеет нетривиальный наибольший общий делитель с числам !9.
(См. ХЕЕЕ Тгапзасс!опэ 1Т-26 (1980), 726-729.) 36. Согласно выражению (4) т-е простое число равно т!птп+т!и!пт — т+т!и!пт/!пш — 2т/!пт+О(т(!об!обт)~(!обт) з), котя для ре)нсиин ПОставЛеннОй ЗадачИ дОстатачнО более слабой оценки р = т!пт+ О(рп !об !об ш). (Пазагаем, что р является ш-м простым числом, учитывая предполаже.)ф рр* =)р) ~к с = 0(1), получим ,=.-'РТ м)м) м-с *- -'))))м)))м)-м-')) )Р)))м о)~7 ) мТ) м). Оценка (22) времени выполнения алгоритма Е несколько неожиданно упрощается: ))),м)т,мямз мр ьем)), где функция /(с, 37) = с+ (1 — (1 + 1и 2)/1п !и Л))с '.
Значение числа с, минимизирующего ф„„)),,м), ~~- )р р . т,, ф р)т т м) ° т м Т вЂ” Т ) 2))) ) м О)) р)чм)). Для Х = 10 эта оценка дает с(!т') .ЗЗ, что по-прежнему существенно превышает результаты наблюдений за поведением процесса. Замечание. Поведение частичных отношений числа оГР подчиняется распределению, полученному в разделе 4.5.3 для случайных вещественных чисел. Например, первый миллион частичных отношений для числа 10'~ + 3141о9 содержит точно (415 236, 169 719, 93 180, 58606) случаев, когда А соответствует (1, 2, 3,4).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
