AOP_Tom2 (1021737), страница 202
Текст из файла (страница 202)
ПоэтомУ е, =1 не, =1. Замечание. Для того чтобы выполняемая проверка оказалась эффективной, следует подбирать Р и Я таким образом, чтобы проверка выполнялась с некоторой вероятностью. Лемер (Еебшег) предложил выбрать Р = 1, чтобы 11 = 1 — 4Я, а Я выбрать таким образом, чтобы Х ~. ЯР. (Если последнее условие не соблюдается, значит, число А' ие простое, если только выполняется условие )(ГВ) < Х.) Далее, из приведенного выше рассуждения видно, что желательна иметь е~ = 1, т.
е. сг~ МШ гй -1 (по модулю Х). Это еще одно условие, налагаемое на выбор Я. Если П удовлетворяет этому условию и если Сгн+~ шог) Х Р О, то известно, что Х вЂ” не простое. Пример. Если Р = 1 и Я = -1, то получаем последовательность Фибоначчи и Р = 5. Поскольку 5'~ ш — 1 (по модулю 23), можно было бы попытаться доказать, что 23— простое число, используя последовательность Фибоиаччн: (Рв пюб 23) = О, 1, 1, 2, 3, 5, 8, 13, 21, Пч 9, 2О, 6, 3, 9, 12, 21, 10, 8, 18, 3, 21, 1, 22, О, . Поэтому 24 есть ранг появления 23, и проверка сработала. Однако при помощи последо- вательности Фибоначчи не удается установить подобным образом тот факт, что числа 13 и 17 — простые, так как 5'г шог! 13 = О и Рэ шоб 17 = О.
Если р ш ш1 (по модулю 10), то 50 Огз шоб р = 1 и, следовательно, Рр ~ (но не Реы) делится на р, 17. Пусть /(д) = 2!89 — 1. Если д = 2 или 3, то дерево содержит не более /(9) узлов. Для простого числа д > 3 положим д = 1 + д~., йн где 1 > 2, а йм ..., Ос — простые числа. Размер дерева < 1+ 2 /(дь) = 2 + /(9 — 1) — ! < /(9). (ЯСОМР 7 (1975), 214-220) 18. Величина х(С(п) — Р(а)) равна количеству таких и < х, для которых второй по величине простой множитель не превышает х, а наибольший по величине простой множитель > х~. Следовательно, *С(1) 21 = ( (*'+") — я( ')) *' '(С(1/(1 — 1)) — Р(Г/(1 — 1))).
Вероятность того, что р~ ~ < „/рп равна / Р(1/2(1 — 1))! 'с!б (Кстати, можно показать, что она равна / Р(1/(1 — 1)) сй, т. е. среднему значению величины (обр~/)об х; она равна и 1 константе Дикмана-Голомба (П!сйшап-Со!ошЪ) .62433, приведенной в упр. 1.3.3-23 и 3. 1-13. Можно показать также, что пронзводнан Со(0) равна ,)е г (г/(! — 1))! ' и! =- г (1) + 2г (-,') + 3г (-,') + = е'. Для третьего по величине простого множителя Н(а) = ! (Н(!/(1 — 1)) — С(1/(1 — 1)))1 61, а Н" (0) = со.
См. Р. В!)!ипбе(еу, Регюс4, Маей. Ннпяаг. 2 (1972), 283-289; Л. Са!ашЬов, Асса АНГЛ. 31 (1976), 213-218: П. Е. Коней, Е. ТгаЬЬ Рагбо, ТЬеогебса1 Согпр. Всб 3 (1976), 321 — 348; Л. 1. На(пег, К. Я. МсСиг!еу, Х А!8огйЛшв 10 (1989), 531-556 ) 19, Число М = 2 — 1 кратно всем числам р, для которых порядок 2 по модулю р и делит число Г1.
Разовьем эту идею, положив а~ = 2 и а +~ = ар шог! 1У, где 91 = р ', рз есть /-е простое число и ез = ()о81000/(обре). Пусть А = а~ее, Вычислим теперь Ьэ = 8сс!(Аг — 1, Х) для всех простых чисел д, расположенных между 10 и 10 . Это можно сделать, если начать вычисления с числа А еее шог! Х, а затем умножить его на Аз шаба шее или А шог)!У. (Похожий метод в 1920 году применил Д.
Н. Лемер (П. Х. ЬеЬшег), но он не опубликовал результатов.) Так же, как и в алгоритме В, можно путем группирования исключить из рассмотрения почти все наибольшие общие делители; например, поскольку Ьзе„ь = бес)(А " — А', Х), можно использовать группы нэ 8. вычисляя сначала с„= зе (Азе" — Аш)(А~" — Аю)... (Азе' — А) шог! Ж, а затем — бег((с„Ж) для 33 < г < 3334. 20. См. Н.
С. %!)!!ашв, Маей. Сошр. 39 (1982), 225-234, 21. Интересная теория, имеющая отношение к условиям этой задачи, была предложена Эриком Бахом (ЕНс ВасЬ), 1пбзгща11оп апИ Сошрпгабоп 90 (1991), 139 — 155. 22. Алгоритм Р не достигает цели только тогда, когда для случайного числа х не подтверждается тот факт, что число и не простое. Будем называть число х влазим, если хг пюбп = 1 или одно из чисел хзй удовлетворяет условию ш -1 (по модулю п) для 0 < У < к.
Поскольку число 1 плохое, получаем р„= (܄— 1)/(и — 2) < 6 /(и — 1), где 5„— количество плохих чисел хь таких, что 1 < х; < и, если число п не является простым. Каждое плохое число х удовлетворяет условию х" ' щ 1 (по модулю и). Если число р простое, числа решений уравнения хг ш 1 (па модулю р') для 1 < х < р' равно числу решений уравнения 99 ш 0 (по модулю р' '(р — 1)) для 0 < 9 < р' ~(р — 1), т. е. 8сг)(д, р' '(р — 1)), поскольку можно заменить число х числом а", где а — простой корень.
Пусть п = и,'...и„'', где все п~ — различные простые числа. Согласно китайской теореме об остатках число решений уравнения х" ш 1 (по модулю п) равно Д,"., 8сб(п — 1, и," '(и< — 1)), и таких решений не более чем П,.',(и, — 1), поскольку число гн взаимно просто с п — 1. Если некоторое е; > 1, та гн — 1 < е и," и, следовательно, число решений не превышает э и; 2 3 в этом случае Ь < ~п < -'(и — 1), нбо и > 9. В связи с этим можно положить, что число п равно произведению пы, .
и, различных простых чисел. Пусть и; = 1+2"' дн где !с~ < < !г, Отсюда получаем 8сб(п — 1, и, — 1) = 2" дз где Ь, '= ппп((г, Ь;) и Ч,' = 8сб(д, д,). При модуле и, количество таких х, для которых нч выполняется условие хе ш 1, равно Ч';, а количество чисел х, для которых х т ш — 1, равно 2зд,' прн 0 < ! < Ь'; и О в противном случае. Поскольку !г > Ьм то Ь„= Ч', ...Ч'„(1+5.„1,„, 2 '). Для завершения доказательства достаточно показать, что Ь < здг...
Ч,2 '+ -'у(п), так как 1с(п) < и — 1. Отсюда получаем (1+ ~ „, 21")/2Ы~"'~Ю < (1+~~(, ь, 2'")/2»'" = 1/(2' — 1) + (2" — 2)/(2~'"(2" — Ц) < 1/2" Следовательно, если не выполняются равенства г = 2 и )с~ = !см получаем результат, Для г = 2 в упр 9 показано, что число и — 1 не кратно как числу п~ — 1, так и числу пз — 1.
Значит, если Ь! = !гш то нельзя получить равенства Ч( = Ч~ и Чэ~ — — Чз; отсюда следует, что в этом слУчае д(дз < зд~дз н Ь„< -'фп). (См. Х ЧднтЬег ТЬеогу 12 (1980), 128-138.) Из этого доказательства следует, что число р, близко к -' только в двух случаях: когда число п равно (1 + 2Ч~)(1 + 4Ч~) и когда оно является числом Кармайкла спепиютьного вида (1 + 2р)(1 -Ь 2дз)(1 + 2дз), Например, для и = 49939 99877 получаем Ь„= -(49938 99876) и р„.24999; если и = 1667-2143 4523, тоЬ = -„'(1ббб 2142 4522), р„.24968.
Дополнительные примечания приведены в ответе к следующему упражнению. 23. (а) Доказательства для всех случаев, кроме, может быть, случая закона обратимости, выполняются просто. Пусть р = рм., р, и Ч = Ч,... д„где все,р, и Чт — простые числа. Тогда ("-) =П('-') =П- " "'" и" ('-') = — "" "" В" (-') д, Ч! р' р так что остается-только убедиться в том, что ~, (р~ — 1)(д! — 1)/4 г— е (р 1ПЧ 1)/4 (по модулю 2) Но 5, (р, — 1)(д — 1)/4 = (2 (р, — 1)/2)(2 .(дз — 1)/2) будет нечетной тогда и только тогда, когда для нечетного количества чисел р, и Чз выполняется га 3 (по модулю 4), а зто происходит тогда и только тогда, когда число (р — 1)(д — 1)/4 нечетно. (С. О.,!.
5асоЬЬ Вег!сбг Коп!8!. Ргеиб. А!гаг1 Иг!ке. Вег!ш 2 (1837), 127-136; В. А. Лебег (5г. А. ЬеЬсебие] в Х ЛХаГЬ. Ригеь Арр!. 12 (1847), 497-520, исследовал действенность этого метода.) (Ь) Так же, как н в упр. 22, можно положить, что и = пы .. и„, где все и; = 1+2цд;— различные простые числа и (г~ < . < Й„положим также, что 8сб(п — 1, ти — 1) = 2 (Ч,'. ь( Будем называть число х плохим, если оно приводит к ошибочной классификации числа и как похожего на простое. Пусть П„= П,", Ч,' 2 ькь"ь М вЂ” число решений уравнения х~" !в : 1. Количество плохих чисел х, для которых выполняется равенство ( — „) = 1, ! — ОЫ к равно П, умноженному на дополнительный множитель з при !и < (г.
(Этот множитель— 1 необходим, чтобы гарантировать выполнение равенства ( — *) = — 1 для четного количества чисел и, прн Ь; < Ь ) Количество плохих чисел х, для которых (-„*) = — 1, равно П„, если Й~ = Й, и 0 в противном случае. [Если выполняется условие х!" ОГ эз — 1 (по модулю и,), то получим в результате ( — „) = — 1 при Ь, = /к, ( — *, ) = +1 и Й! > /к и противоречие, если Ь, < /к.
Если /к! = /к, то существуют нечетные количества чисел йо равных /к.[ Захкечаипе. Вероятность того, что выбор плохой, будет > „-' только тогда, когда и— число Кармайкла, для которого Ьк < /к! например! и = 7 13 19 = 1729, число, ставшее известным благодаря Рамануджану (Па!папа/ап) в другом контексте. Этот анализ был продолжен Луисом Моньером (Еошэ Мотет) при получении следующих формул в замкнутом виде для количества плохих чисел х в общем случае: (1+ 2 1 ) ПО'' Ьч б„Пбс!/( —, и, — 1). =1 =! Здесь Ь'„— количество плохих чисел х в этом упражнении, а б„равно либо 2 (если Ь! = Ь), либо -' (если /к; < /к и е, является нечетным для некоторого ! ), либо 1 (в остальных к чу чаях).
(с) Если х" то!/ и = 1, .то 1 = ( — '„) = („— *)ч = (-„*). Егчи х~ ч = -1 (па модулю и), то порядок х по модулю и, должен быть нечетным кратным числа 2кт' для всех простых делителей и, числа и. Пусть и = и",... и,'." и и, = 1+ 2к+'9,'; тогда ( — ') = ( — 1)ч, так что (-„*) = +1 или — 1 в зависимости от того, какой будет 2 е 9,' — четной или нечетной Поскольку и гн (1 -!- 2к+' 2,' е!9,') (по модулю 2кт~), сумма 2 е,9,' будет нечетной тогда н талька тогда, когда / + 1 = /к.
[ТЬеогейса/ Сошр. Ясб 12 (1980), 97-108.) 24. Пусть М! — матрица, имею!цая ио одной строке на каждое нечетное непростое число и в интервале 1 < и < А!, и А! — 1 столбцов, пронумерованных от 2 до Ак. Значение элемента, расположенного в строке и и столбце х, равно 1, егли проверка чик ча и !шгоритыом Р посредством х дает отрицательный результат, и равно 0 в остальных случаях Известно. что если /ч' = ди+ г и 0 < г < и, то в строке и содержится не более — 1 + 4(Ь„+ 1) + тт(Ь„+ 1,г) < 9(ч(и — 1)+1)+тт(Ь„+1, г) < зйи+т1п(-'и, г) = -чй Ьт!и(-'к! — -'г, 2г) < -' Х+ -'и < -'Лк элементов, равных 0; поэтому по меньшей мере половина элементов матрицы равна 1, Тогда в некотором столбце х! матрицы М! хотя бы половина элементов равна 1.
Если вычеркнуть столбец х! и все строки, элементы которых в этом столбце равны 1, то получится матрица Мэ со свойствами, подобными свойствам матрицы М!. Повторно выполнив описаннучо процедуру, можно сформировать матрипу М,. которая имеет /ч — г столбцов и число строк, меньшее Ак/2', и которая содержит не менее ! (!!' — 1) эчементав, равных 1. [См. КОСЯ 19 (1978), 78.] [Подобным образом может быть доказано существование единственной бесконечной последовательности х! < хэ <, такой, что число и > 1 будет простым в том и колько в том случае, если его проверка выполнена алгоритмом Р посредством х для х = х!, х = х „где т = -'[!8и)([!8и) — 1). Существует ли последовательность, обладающая такими же свойствами, но в случае, когда гп = 0(1об и)7] 25.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
