AOP_Tom2 (1021737), страница 125
Текст из файла (страница 125)
(33) При р ф 3 по теореме Ферма имеем Зг ' = 1; следовательно, (З~г Ц»э — 1) х (3<э Ц»х + 1) = О и 31г '17»вЂ” : ~1. Если У = — 1, то П ~» —— 4П вЂ” П 4Гр + 1р 6р».» = Пг».»' отсюда й~р+» шеар = О. Если Ур +1 то г р 4~я с»г»-» = 41»г 1р — ю㻠— = — 0р», .значит, Ур» шо»(р = О. Хаким образол» доказано, что для каждого простого р существует целое число е(р), такое, что (Зб) бр+мы шо»1 р = О, (с(р)) < 1. Далее, если 1»' — произво * чое положительное целое число и если»п = »п(Л)— такое наименьшее положительное целое число.
что с7 ~»»1 пнк1»»' = О, то У„шод Х = О тогда и только т~ ла, когда и кратно»п(»»'). (37) (Это число т(11») называется рангом появления в последовательности числа У.) Для доказательства (37) учтем, что последовательность К„, С', ».м Г„,+»,... конгруэнтна (по модулю х) последовательности ас»э, а(»м ап», ..., где число а = с» э» щи»» взаимно просто с»т, так как бсп(П„, Е'„».») = 1. После всех этих приготовлений докажем теорему Ь. В силу соотношения (27) по индукции имеем Е„= Гг шос( (2» — 1).
(38) Далее, из тождества 2Г„+» = 4с7„+ 1~„следует, что бед(У„, 1'„) < 2, поскольку всякий общий делитель чисел 17„и 1;, должен делить У„и 2У„».м в то время как б;, 1. 6'„».м Поэтому У„и Г„не имеют общих нечетных множителей, и, если .б»-э = О, долж~о ~ы~о~~~~~с~ С'м-~ = Схю — »Ъм — г = О (по модулю 2 — 1), Сы — ~ О (по модулю 2' — 1). Затеи, если т = гп(2» — 1) — ранг появления числа 2» — 1, то оно должно быть делителем Числа 2» ', но не числа 2»»; таким образом, т = 2» '.
Докажем теперь, учитывая сказанное выше, что число и = 2' — 1 должно быть простым. Предположим, что разложение числа и на простые множители имеет вид р",... р',". Все простые числа р, больше 3, так что число и нечетно и конгруэнтно ( — 1)» — 1 = -2 (по модулю 3). Из (ЗЗ), (Зб) и (37) следует, что Ц: — О (по модулю 2» — 1), где $ = 1сш(р»~' (р» + с~), ..., р'„' '(р„+ с,)), н каждое еу равно х1. Отсюда получаем, что 1 кратно»п = 2» '. Пусть пе —— Д1, р ' (р +»1); тогда пр < 1(., р ' (р, + -',р.) = (»)"и.
Кроме того, поскольку р + еу — четное число, то 1 < пе/2" ', ибо всякий раз, когда берется наименьшее общее кратное двух четных чисел, л»ножитель 2 теряется. Объединяя эти результаты, получаем т < 1 . 2(э)"и < 4(~1)"т < Зт; отсюда, г < 2 и 1 = т ьли 1 = 2»п, т. е. 1 равно степени 2. Поэтому е» = 1, е„= 1 и, если и — не простое число, должно быть и = 2» — 1 = (2ь + 1)(2' — 1), где 2" + 1 и 2' — 1 — простые числа. Последнее разложение при нечетном д невозможно, поэтому и — простое. Обратно, предположим, что и = 2г — 1 — простое число. Необходимо показать, что 'гы- гя О (по модулю и). Для этого достаточно доказать, что )гз,— = -2 (по модулю и), поскольк>' >'за-1 = (1зе — в) — 2.
НО 2- ~; ( + )ьг2"+'-'"дэа 21>- »г~ ~("+ ) 3 Так как и — нечетное простое число, биномиальный коэффициент ( 2к ) (2к) (2(с — 1) делится на и за исключением случая, когда 2к = О и 2к = и + 1. Следовательно, 2>а '>7~12,-~ = 1+ 31"+'»з (по модулю и). Здесь 2 = (2('+'>72)з, поэтому согласно теореме Ферма 2>в '>/з = (2>е+»/з)>а '> = 1. В итоге в силу одного простого случая закона взаимности квадратичных вычетов (упр. 23) 3>а '>/з— : — 1, поскольку и шод 3 = 1 и и >нос(4 = 3. Это означает, что Гз~- — = — 2 и, следовательно, должно быть гж-~: — О, что и требуется. ! В 1460 году анонимный автор, работы которого в настоящее время хранятся в итальянских библиотеках, открыл, что числа 2'7 — 1 и 2'е — 1 являются простыми [см.
Е. Р>сц111, Н>всог>а МасЬ. 16 (1989), 123 — 136]. С тех пор наибольшими из известных простых чисел почти всегда оказываются числа Мерсенна. Но положение может измениться, поскольку. находить простые числа Мерсенна становится все труднее, и поэтому в упр. 27 представлен эффективный способ проверки чисел другого вида. УПРАЖНЕНИЯ 1. [10] Если последовательность пробных делителей в алгоритме А Ые, А, Ыз, ... содержит число, не являющееся простым, то почему оно никогда не появится на выходе? 2. [15] Можно ли исключить из алгоритма А шаг А2, егля известно, что исходное число >У для алгоритма А не меньше 3? 3.
[М20] Покажите, что существует число Р со следующим свойством: если 1000 < и < 1 000 000, то число и будет простым тогда и только тогда„когда йсб(п, Р) = 1. 4. [Мйй] Используя обозначения упр. 3.1-7 н раздела 1,2.11.3, докажите, что среднее значение наименьших и, таких, что Х„= Хц„> ы находится в интервале между 1.5(г(т) — 0.5 и 1.02512(гп) — 0.5. 5. [21] При помощи метода Ферма (алгоритм 1>) найдите вручную множители числа 11 111 по модулям 3, 5, 7., 3 и 11.
б. [М24] Докажите, что если и — нечетное простое число и Х не кратно числу и, то количество целых чисел х, принадлежащих интервалу 0 < х < р, для которых существует решение 0 уравнения х~ — М гэ у' (по модулю и), равно (р х 1)/2. 7. [25] Проанализируйте задачи программирования метода решета — алгоритм П вЂ” для двоичного компьютера в с зучае, когда табличные значения для модулей т, заполняют не точно целое число слов памяти.
° 8. [93] (Решены Эратосфена, 3 в. до н, з.) Следующая процедура позволяет найти все нечетные простые числа, меньшие данного целого числа?У, поскольку она удаляет все непростые числа. Выполнение процедуры начинается с того, что для всех нечетных целых чисел от 1 до Х последовательно вычеркиваются числа рззм рь(рь + 2), рь(рь + 4), кратные 9-му простому числу рь прн и = 2, 3, 4, ..., пока не будет найдено такое простое число рю длн которого рь ~> Ю. Покажите, как превратить описанную процедуру в алгоритм, пригодный для прямой реализапии в компьютере, без использования операций умножении.
9. [М25] Пусть и — нечетное целое число и и > 3. Покажите, что если число й(п) из теоремы 3.2.1.2В является делителем числа и — 1, но не равно и — 1, то и должно иметь нид р)рэ...рн где все р, — различные простые числа и 1 > 3. ь 10. [МЯ5] (Джон Селфрцдж (1оЬн ЯеДпббе).) Докажите, что если для любого простого делителя р числа и — 1 существует такое сю что я " ' " шос(п ф 1, а к" ' шодп = 1, то в — простое число. 11. [М30] Что выведет алгоритм Е, если )У = 197209, Й = 5, т = 7? ~У . 'ГЫГ2И = 992 +ГГЗ91 2 ШЭ ~98~/Д ь 12. [М25] Разработайте алгоритм, который, используя выходные данные алгоритма Е, находит подходящий простой множитель М, который обеспечивает возможность алгоритму Е формировать достаточно данных для вывода решения уравнения (18).
13. [НМ95] (Дж. Д. Диксон (3. П. Ейхоп).) Докажите, что как только алгоритм из упр. 12 предстакчнется решением (к, ее,..., е ), показатели степени в котором линейно зависят по модулю 2 от показателей степени в предыдущих решениях, когда число Х имеет различные простые множители, а величина х выбирается случайно, вероятность того, что разложение на простые множители не будет найдено, равна 2' 14. [МЯ0] Докажите, что прн выполнении шага ЕЗ алгоритма Е число 2" никогда не кратно нечетному простому множителю р, для которого выполняется неравенство (й?у)1" П?~ шос) р > 1. ь 16. [М34] (Люка (1 исав) и Лемер (1,е1ппег).) Положим, что Р и Я вЂ” взаимно простые целые числа, и пусть Пе = О, (?~ = 1, (?„э.~ = Р(? — с4(?„~ при и > 1.
Докажите, что если Ю— положительное целое чисто, взаимно простое с числом 2Р— 8Я, и если (7ячч шос(?У = О, а (71яээур шоб Х ~ О для каждого простого числа р, делящего Ю + 1, то ?У вЂ” простое число. (В результате получаем метод проверки принадлежности чисел к простым числам в случае, когда известны делители числа Х + 1, а не делители числа М вЂ” 1. Значение 17„, можно вычислить за О()об т) шагов, как а упр. 4.6.3 — 26.) [Указание.
См, доказательство теоремы Ц 16. [М50] Бесконечно ли множество простых чисел Мерсенна? 17. [М25] (В. Р. Пратт (У. В. РгаМЦ Полное доказательство принадлежности чисел к простым при помощи обратной теоремы ферма принимает вид дерева с узлами (д, х), где д и х — положительные целые числа, удовлетворяющие следующим условиям. (1) Если узлы (4пк~),, (дик~) порождены узлом (О,г), то о = ды .. д, + 1. [В частности, если (д,г) — младший потомок, то 4 = 2.] (й) Если узел (г,у) порожден узлом (д,к), то яы-юl" шейд ф 1. ()п) Для каждого узла (7,к) выполняется условие х' ' шаба = 1.
Из этих условий следует, что число (7 простое и х есть простой корень по модулю (7 дэщ всех узлов ((7, х). [Например, дерево (( 9, ) (2,() (2,() (2, ) (),() (),)) (), ) (),2) (2, 1) (3, 2) (2, 1) (2, 1) [ (2, 1) показывает, что 1009 †прост число.[ Докажите, что подобное дерево с корнем ((7,х) содержит не более У((!) узлов, где функция 7' довольно медленно возрастает.
ь 13. [НМ39[ Приведите эвристическое доказательство соотношения (7) по аналогии с выиодом соотношений (6), рассмотренных в этом разделе. Чему равна приближенная вероятность того, что р, ) < ~/р(7 ь 19. [М25[ (Дж. М. Поллард (9. М.
Ро!!агф) Покажите, как вычислить число М, которое делится на все нечетные простые множители р, такие, что р — 1 является делителем некоторого заданного числа В. [Указание. Рассмотрите числа вида а" — Ц Такое число М полезно при разложении чисел на простые множители, поскольку множитель числа Х может быть получен в результате вычисления йс(((М,Х).
Постарайтесь развить эту идею и сформулировать эффективный метод нахождения с высокой вероятностью простых множителей р данного числа й) для случая, когда все простые степенные множители для чисел р — 1 меньше 10э, кроме, может быть, одного, меньшего 10 . [Нш)ример, при помов)и такого метода будет обнаружен второй по величине простой множитель, который делит (15), так как он равен ) + 2 5~ 67 107. 199 41231.] 20.
[М40[ Рассмотрите упр. 19, подставив в условие р+ 1 вместо р — 1, 21. [М49) (Р. К. Ги (В., К. Оиу).) Пусть гп(р) — число итераций, необходимых алгорит- му В длн выделения простого множителя р. Будет ли выполняться равенство гл(р) = О(~lр!ойр) при р -+ оо? ь 22. [М90[ (М. О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
