AOP_Tom2 (1021737), страница 201
Текст из файла (страница 201)
Примечательно, что 11 111 = 8616 460 799 (по модулю 3 7 8 11), поэтому уравнение (14) справедливо и для /д = 11 111 за исключением случая, когда модуль равен 5, Поскольку при вычислении (хг — Х) пюс1 5 остатки равны 4, О, 3, 3, О, должно быть х шог) 5 = О, 1 или 4. Первая проба х > [т/гг" ] = 106, при которой удовлетворяются все условия, дает х = 144; но вычисление квадратного корня из числа 144г — 1, 111 = 9 625 не дает в результате целое число.
Однако следующая проба дает 156 — 11 111 = 13 225 = 115г, и в результате получаем 11111 = (156 — 115) (156+ 115) = 41 271. 6. Подсчитаем число решений (х,у) конгруэитных уравнений Л = (х — у)(х+ у) (по модулю р), где 0 < х, у < р. Поскольку Л' 81 О, а р — простое число, та х + у у! О. Для каждого о ~ 0 существует единственное и (по модулю р), такое, что Л' ш ве. Далее, так как р — простое число, конгруэнтные уравнения х — у ш и, х + у г— в о однозначно определяют хшабр и у шаг)р. Таким образам, указанное выше уравнение имеет точно р — 1 решений (х,у).
Если (х,у) — решение, то (х,р — у) тоже является решением при у т' О, так как (р — у)г ш у; и, если (х, уг) и (х, уг) — решения, для которых уг ЭЕ уг, то уг щ уг откуда уг = р — уг. Таким образом, количество различных значений х среди г г решений (х,у) равно (р — 1)/2, если уравнение )г' ж х не имеет решений, или (р+ 1)/2, если Л" = х имеет решения, 7. Одно нз возможных решений состоит в том, чтобы для каждого модуля иметь два индекса; один — для адресации текущего слова, другой — для адресации текущего бита; загрузка двух слав таблицы и выполнение индексированной команды сдвига подравняет элементы таблицы.
(Такичи операциями манипулирования битами оснащены многие компьютеры.) 8. (Можно положить, что )г' = 2М, т. е. четио.) В следующем алгоритме используется вспомогательная таблица Х[1], Л [2],..., Х[М], где в Х[/с] отражен признак принадлежно- сти числа 2/г -~-1 к простым числам. 81. Присвоить Х[/г] г- 1 для 1 < Ь < М. Присвоить также 7 +- 1, р +- 3, д +- 4. (В ходе выполнения этого алгоритма р = 27 + 1 и д = 22 + 2/~.) Б2. Если Х[Я = О, то перейти к шагу Б4, В противном случае вывести р, которое является простым, и присвоить Й +- д. Б3. Если й < М, то присвоить Х[Ц е — О, /с г- /с+ у и повторить этот шаг.
Б4. Присвоить 7' +- 3+ 1, р г- р+ 2, д +- д+ 2р — 2. Если 7' < М, то возвратиться к шагу Б2. 3 Можно заметно ускорить ббльшую часть вычислений, если на шаге 84 сравнить с М не /, а д, и добавить новый цикл, который, подавляя манипуляции р и д, выводит 2/+ 1 для всех оставшихся Х[Я, равных 1. Замечание. Оригинальное решето Эратосфена было описано в книге 1, главе 13 сочинений Никомаха (741согпас!шэ) )псго8исс1ов со АпсЛпгейс, Хорошо известно, что [р )г"]/р = 1в 1в)г'+ М+ О((1об Л') ), где М = Т+ 2 ь р(Л) !пай)/Л вЂ” константа Мертенса, равная 0.26149 72128 47642 78375 54268 38608 69585 90516; 993г = -!-2г сч.
Г. Мег!евэ, Сге!!е 76 (1874), 46-62; Сгеепе, КппгЬ, Ма!Лета!ни 7ог гЛе Ала!уз!з о7 А!8огВЛшэ (Воэ!оп: В!гЬЬапэег, 1981), 14.2.3. В частности, число операций, выполняемых оригинальным алгоритмом Никомаха, равно Х !и !в Ау+ 0(Х). В упр. 5 2 3-15 н разделе 7 1 рассматриваются пути повышения эффективности методов просеивания для геиернрования простых чисел. 9. Если р — делитель числа и для некоторого простого числа р, то р есть делитель чнгта Л(п), но не числа и — 1. Если и = ргрг, где рг < рг — все простые числа, то рг — 1 являнгся делителем числа Л(п), и поэтому ргрг — 1 = 0 (по модулю рг — 1).
Поскольку рг = 1, то р, — 1 кратно рг — 1, но это противоречит предположению, что рг < рг. [Значения п, для которых Л(п) есть собственный делитель числа и — 1, называются числами Клрмаггкла (СагпнсЬае1). Например, приведем несколько малых чисел Кармайкла, содержащях более шести множителей: 3 11.17, 5.13 1?, 7 11 13 41, 5.7 17 19 73, 5 7 17 73 8% 107 Имеется 8 241 число Кармайкла, меньшее 10'г, и существует хотя бы П(Жщг) чисел Кармайклэ, меньших Х [см.
Ж. В. А!Еогб, А, Сгапт!!!е, С. Раогегапсе, Алла)э о7 ЫагЛ. (2) 139 (1994„ 703-722]. 10. Пусть Лр — порядок числа хр по модулю и и Л вЂ” наименьшее общее кратное всех таких Л„. 'Тогда Л является делителем числа и — 1, но не делителем любого (и — 1)/р, поэтому Л = и-1. Поскольку к„" шод и = 1, то Г(п) кратно Лр для всех р; следовательно. я(ч) !р(п) > Л.
Но !г(п) < и — 1, если п — не простое числа. (Другой способ доказательства заключается в том, что при помогли метода, рассмотренного в упр. 3.2.1 2 15. нз элементов хр строится элемент х, имеюгций порядок и — 1.) 11. и Г А Р З т Выход 1984 1 0 992 0 1981 1981 1 992 1 1981 1983 4 495 993 0 1 1983 991 2 98109 1 991 1981 4 495 2 О 1 2г щ +2г 1984 1981 1 99099 1 1981 1984 1 1984 99101 0 1 99101г щ +2а Разложение 199 991 получается из первых или последних выходных данных. Краткость цикла и появление хорошо известного числа 1984 †э, вероятно, просто совпадение 12. В следующем алгоритме используется вспомогательная (т+ 1) х (го+ 1)-матрица с целочисленными элементами Егь, 0 < 1, Л < т, входной вектор (Ьа, Ьп -, Ь,„) с элементами однократной точности и вектор (ка,хм,.,,к ) с элементами многократной точности, заданными в интервале 0 < хь < Х Г1.
[Начальная установка.] Присвоить Ь, е- — 1 для О < г < гл; затем присвоить ! ь- 0 Г2. [Очередное решение.] Из алгоритма Е взять очередное решение (х. со, ег,..., е„). (Алгоритмы Е и Г удобно рассматривать как сопрограммы.) Присвоить Л <- ш. ГЗ. [Найти нечетное число.] Если Л < О, перейти к шагу Г5. В противном случае, если еь четно, присвоить Й г — Л вЂ” 1 и повторить этот шаг.
Г4. [Векторы линейно зщгисимы7] Если Ьь > О, присвоить г +- Ьь, х +- (х,г) шоб Х, е +- е, -!- Е,„для 0 < г < т; присвоить Л г — Л вЂ” 1 н возвратиться к шагу ГЗ. В противнол, случае присвоить Ьь ь- 1', хг +- х, Е,„ь- е, лля О < г < т; присвоить 1 г- г + 1 и возвратиться к шагу Г2.
(В последнем случае получаем новое линейно независимое решение по модулю 2, первым нечетным компонентом которого является сь. Значения Ег, могут и не быть значениями однократной точности, но онн, скорее всего, будут оставаться малыми при уменьшении Ь от т до 1 согласно предположениям Моррисона (Могг1эоп) н Бриллкарта (ВП11!гааге).) эб. (Попытаться выполнить разложение.) (Теперь ее, ем .,., е четные.) Присвоить р г- ((-1) '~ р,'~ ..р ) шодХ. Если х = у или х+у = А', возвратиться к шагу Г2.
В противном случае вычислить йсй(х — у, А'), который является собственным делителем числа Ю, и завершить выполнение алгоритма. $ Этот алгоритм находит простые множители, когда есть возможность найти множитель из танного набора результатов алгоритма Е. (лекаэательсшео. Пусть результатами выпол~ения атгорнтма Е будут (Х„Е,е,..., Е„) при 1 < 1 < Г, и положим, что удалось найти разложение на простые множители числа РЬ = У~А'ж когда выполняются соотношения х = Х ..
Х ну ш ( — 1)ышр",~~... р' ~~ (по модулю Х), где е = а,Е,,+. +а~Е, четно для всех 1. Тогда х: — ху (цо модулю А',) и х гв хр (по модулю Х~). Нетрудно увидеть. что зто решенве можно преобразовать в пару (х, у), которая появляется при выполнении шага Г5, путем выполнения ряда операций, на которых пары (х, у) последовательно гаменяются парами (хх, уу ), где х ьз ху (по модулю Х).) 13. Имеется 2 значений величины х, имеющих одинаковые показатели степени ь (еа,,е ), поскольку, если Ю = д~'...
д„", знак величины х по модулю о,' можно выбирать произвольно. Множители отсутствуют точно для двух из этик 2 значений. г 14. Поскольку Р ш ЙЮЯ~ (по модулю р) для любого простого делителя р числа Ъ', получим 1 ш РЦ" 'кэ = — (ЬХЦэ)~г ОГз гя (/сХ)ш 'пэ (по модулю р) при Р ф О. 15.
П = (а" — Ь")! И, где а = -'(Р1- ~/Р), Ь = -'(Р— ьгЪ), .0 = Р— 4Я. Тогда 2" 'У )' „(,ь.ь,)Р 11; поэтому Уг ш ПШ '~~~ (помодулюр), если р — нечетное простое число. Аналогично, если 1в = а" + Ь" = ~У„+~ — Ясг и то 2" '1'„= 2 (" ) Р" ы1уь и ~~р = Рг ш Р. Таким образом, если Ур = — 1, получаем, что Ог+~ пюбр = О. Если Ур ш 1, то (ЦЦ, ~) гподр = О.
Здесь, если Я кратно р, то сГ ш Р" (по модулю р) для и > О, поэтому П никогда не будет кратно р; если Я не кратно р, то ЬГр ~ шог(р = О, Поэтому, как и в теореме 1., Ц шой Х = О, если Х =р",...р',", Х 2. Ц и С = 1ст~с,с,(р," (рг+сэ)), При предположениях из этого упражнения ранг появления числа Х равен Ж+ 1; значит, Х взаимно просто с с), а 1 кратно А' + 1. Кроме того, из предположений этого упражнения следует, что каждое рз является нечетным и каждое сг равно х1, поэтому ИР,~ (Рг + УРз) = 2(-)" Д'; слеДовательно, г = 1 и С = Р" ,+ с~Р" ,.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
