Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 82
Текст из файла (страница 82)
Поскольку ог6„6 [ ф(п) для любого целого числа Ь и ф(п) = 6 для п = 14, порядок каждого 6 в (1, 3, 5, 9, 11, 13) можно легко подсчитать, как это было сделано для а = 5. огд„Ь 1 3 5 9 11 13 ТЕОРЕМА 10.33. Если НОД(а,п) = НОД(Ь,п) = 1 и огс[„а является взаимно простым с огг)„6, то огй„(аЬ) = (огй„а) . (ог6„6). ДОКАЗАТЕЛЬСТВО. Пусть огг)„а = В и огг)„Ь = о, тогда (аЬ)~~ = аизбнз = (а ) (Ьз)Я = 1 1 а— е 1 (шоб п). По теореме 10.31, огг[„(аЬ) [ Во. Поскольку числа В и о — взаимно простые, то существуют целые числа г и з, для которых ога„(аЬ) = гз, г ив = В и з.
х = о'. Покажем теперь, что г = В и з = о'. По определению г и з, (аЬ)"' = а"'6вв = 1 (аввбвв)вв 1вв (а в)в (Ьви )в (шаг[ п); (той п); (гаог1 и). Но поскольку а' = 1 (пюг) и) и гш = В, имеем Ьдв=1 ( ап). По теореме 10.3Ца) имеем ог6„6 [ Вз или, что то же самое, В [ Вз. В силу того, что НОД(В,о) = 1, имеем о [ з, но также з [ о, так что 3 = з. Аналогично, В = т. Таким образом, огг)„(аЬ) = (огй„а) .
(огг)„6). Если гп = 4, то 5 = 9 (гной 14), но огйы 5/НОД(оглы 5,4) = 6/НОД(6,4) = 6/2 = 3. Согласно таблице порядков огбы 54 = 3 [теорема 10.3Цд)]. Только Ь = 3 и Ь = 5 имеют порядок 6 по модулю 14. Показателями степени т в таблице, приведенной выше, определяющими значение а, которое сравнимо либо с числом 3, либо с числом 5, являются гп = 1,5,7,11, и 13.
Это только такие значения т, которые являются взаимно простыми с числом и = 14 [теорема 10.3Це)]. П РАЗДЕЛ 10.5. Порядок целого числа 443 ПРИМЕР 10.34. Если п = 11, то все приведенные вычеты являются взаимно простыми с и. Таблица порядков по модулю 11 имеет вид Вычет Порядок Вычет Порядок 1 10 5 5 5 6 7 8 9 10 10 10 10 5 2 [[25 ]] 1 25 2 45 4 53 7 1 Поэтому огйзз 25 = 7, и нет необходимости проверять и = 14 и 28. П Результаты, полученные в теоремах 10.31 и !0.36, приводят к формулировке критерия, названного критерием простоты числа Лукаса.
ТЕОРЕМА 10.36. (Лукас) Если п — целое положительное число, и существует такое целое число а, что а" = 1 (пюй п) а к ф1 (гной п) для каждого простого числа р, которое делит и — 1, тогда п — простое число. Если а = 3 и Ь = 10, то аЬ = 30 = 8 (гаой 11). Таким образом, огйы (аЬ) = огйы(30) = огйы 8 = 10 = (огйы 3) (огйы 10). Безусловно, НОД(3,11) = НОД(10, 11) = 1, огйы 3 = 5 и огйы 10 = 2 — взаимно простые. Заметим, что если а = 3 и с = 7, то огйгг 3 = 5 не является взаимно простым с огйг| 7 = 10. В этом случае огйы(ас) = огйы 21 = огйы 10 = 2 ~ (огйы 3) (огйы 7) = 50. П ПРИМЕР 10.36. Порядок а = 5 по модулю п = 14 был получен в примере 10.32 при вычислении а™ для т = 1,2,3,...,ф(и) вплоть до нахождения того, что а = 1 (гаой и). Из теоремы !0.31(б) следует, что порядок а по модулю и должен делить ф(и); поэтому вместо проверки по одному каждого т, 1 < т < ф(п), тестируются только те значения т, которые делят ф(п).
Для п = 14 ф(п) = 6, единственными положительными делителями которого являются 1, 2, 3 и 6. В данном случае работа по определению огйы 5 сокращается незначительно, поскольку в примере !0.32 значения т = 4 и 5 были уже протестированы. Однако, для п = 58 и а = 25, используя теорему 10.31(б), легко получаем огй з 25 = 7. ф(58) = ф(2. 29) = (2 — 1)(29 — 1) = 28 = 2з 7. Единственными положительными делителями числа 2з 7 являются 1, 2, 4, 7, 14 и 28. Приведенную ниже таблицу легко построить: 444 ГлдееА 10. некоторые специальные вопросы теории чисел ДОКАЗАТЕЛЬСТВО. Из соотношения а" 1 са 1 (шог( п) следует, что НОД(а, и) = 1, а также, по теореме 10.31(а), что ог11„а ( (и — 1).
Если число р — простое и такое, что р ( (и — 1), тогда из сравнимости а1" 01г ф 1 (гпос) и) следует, что огг1„а [ [(и — 1)/р[, потому что, если ог11„а ( [(и — 1)/р[, это противоречило бы а'"д" ' = 1 (шог1 п). Но огг1„а ( (и — 1) и огг1„а 1" [(и — 1)/р[ для всех р, которые делят п — 1, откуда следует, что ого)„а = п — 1. По теореме 10.31(б), ф(п) = п — 1. Поэтому, согласно следствию 10.21, п — простое число. Для того чтобы использовать критерий Лукаса для проверки и, необходимо уметь раскладывать на множители число п — 1, что само по себе может представлять трудности. Более того, требуется находить соответствующее а. Целое число а, введенное в теореме !0.36, называется примитивным корнем числа и.
Используя критерий с числом а = 7, можно показать, что число Мерсенна и = 22' — 1 является простым, поскольку и — 1 = 2 32 7 11 31 151 331. Смотрите упражнения в конце данного раздела. Если НОД(а,п) = 1 и число п — простое, теорема Ферма утверждает, что а" ':— 1 (шог1 и). Ее обобщение, теорема Эйлера, для любого положительно- ГО ЧИСЛа и даЕт ао1"1 е— а 1 (ШОЕ1 и). ИСКЛЮЧая Этн И НЕКОтсрЫЕ друГИЕ СЛуЧаИ, вычисление а' по модулю п или, более точно, вычисление [[а'[[„, т.е, остатка от деления ае на и, для большого значения е может представлять значительные трудности, поскольку само вычисление а' в таких случаях и деление его на и практически нецелесообразно.
В предыдуших примерах мы использовали запись е = е1 + ез +... + еь с соответствующими е,, вычисляли [(а" [[„, перемножали результаты и приводили произведение по модулю п. Этот метод работает, поскольку (И(. = [[иди. П1((. ((„ При этом значения ег были выбраны специальным образом. Более эффективный алгоритм вычисления подобен рассмотренному выше, но использует двоичное представление показателя степени е, т.е. представление на основе числа 2. А именно, е=Ь 2 +Ь 12 1+ +6121+Ьо= = [ЬтЬт — 1 ' 6160(деоичное ~ где Ь, = 0 или 1 и 6 = 1.
Таким образом, е Ь 2 1-Ь е2 -~-" Ч-Ь!2 -~-Ьо Если в выражении для показателя степени сделать перегруппировку с тем, чтобы сократить количество сомножителей, получим представление в соответствии с правилом Горнера: е = ( ((Ь 2 + Ь 1) 2 + Ь 2) 2 + + Ь1) 2 + Ьо, так что ие ( ((пь '2 иь — 1)2 иь — е)2 ..., иье)2 иьо РАЗЙЕП 10.5. Порядок целого числа 445 Мы можем найти значение [(а']]„, последовательно вычисляя выражения в скобках в порядке их вложения, начиная с внутренних, и приводя каждое произведение по модулю и. Таким образом, для е = [Ь Ь 1 ..Ь1Ьо]з„„„„, начинаем с р = ((а]]„. Затем для /с = т — 1, пт — 2, ..., 2, 1 и 0 вычисляем [ [рак,,Ц если Ьь = 0; [[рь г аЦ если Ьь = 1.
Окончательным результатом является ро = ([а']]„. Более подробно, начиная с р = ((а]]„, получаем следующее произведение рь, возводя в квадрат предыдущее произведение и приводя полученное по модулю и, когда Ьь = 0; возводя в квадрат предыдущее произведение, умножая его на а и приводя полученное по модулю и, когда Ьь = 1.
Алгоритм работает, поскольку если а возводится в квадрат Ь раз, результатом будет аз; а если аз Ь возводится в квадрат У раз, в результате получится аз 'Ьз'. ПРИМЕР 10.37. Предположим, что необходимо вычислить[[З~~~Ц,. Поскольку 103 = 2' + 2' + 2з + 2' + 1 = = 1100111 и гп = 6, получаем рь = [[рь а "1] Поэтому [[3'озЦ , = 14. Используя сравнимость по модулю 41 специальным об- разом, получаем 31о 57049 9 Ззо [Зго)з дз бд049 9 Зщ~ Ззо Ззо Зз 9 9 27 2187 14 ° УПРАЖНЕНИЯ !. Докажите малую теорему Ферма в такой формулировке. Если р — простое число и а ф 0 [пюй р), то а" з зв 1 [гаог1 р).
6 5 4 3 2 1 0 3 э— з 3 Зг 3 27 [27)з = 729 г— а 32 [32) = 1024 = 4 (40)з 3 = 4800 = 3 [З)з . 3 = 27 [27)з 3 = 2187 э— з 14 7. Докажите, что для каждого простого числа р (а + Ь)л ве а~ + Ь" (той р). 8. Докажите теорему, обратную к теореме 10.31(а): если и — целое положительное число, НОД(а, и) = 1, 14 = огс)„а и 1. ~ тп, то а = 1 (пю41 т). 9. Определите огб„а для 1 < а < и — 1, если а) п=9; б) п=20; в) п=27. 10. Покажите, что 11. Покажите, что 12. Покажите, что 13.
Подсчитайте следующие вычеты: а) [[3"']] б) цббббоц В) [[1124б81]] г) Ц34971боооо]] ) [[72 3 7 11 31.331]] [[71422174б]] (Для выполнения этого ] гз! 2147483б47 задания вам, вероятно, потребуется использовать компьютер.) 14. Покажите при помощи критерия Лукаса, что следующие числа являются простыми: а) 37; б) 199. 4 б 6 ГЛАВА 7П. Некоторые специальные вопросы теории чисел Докажите, что если НОД(а,т) = 1, то сравнение ах а— э Ь (пюг) т) имеет решение х = а41 ) 'Ь (щог) т).
Пусть р — простое число, р > 2 и 7 = 0 (шоб (р — 1)). Докажите, что 1 +2 +3 + ° +(р — 1) = — — 1 (шог)р). Пусть НОД(т, и) = 1 и пусть множества (71, гг,..., г ) и (81, 82,,, 8„)— полные системы вычетов по модулю гп и и соответственно. Докажите, что множество тп целых чисел (и г; + т 8: 1 < 1 < тп и 1 < 7' < п) представляет собой полную систему вычетов по модулю тп. Восполните все детали доказательства малой теоремы Ферма, используя формулу бинома Ньютона и индукцию по а. Используйте метод упражнения 2 для решения таких сравнений; а) 5х = 8 (пюй 11); б) 7х = 8 (шо11 25); в) 9х = 13 (пюс1 25). а) 61б — 1 делится на 11, если 6 и 11 — взаимно простые числа; б) 6'о" — 1 делится на 11, если НОД(6,11) = 1; в) Ьт — Ь делится на 42 при любом целом Ь. а) 74 = 1 (шог) 5); б) 74 = 1 (пюг) 2); в) 74 = 1 (птоб 10); г) 74" = 1 (пюй 10) для любого положительного целого числа 13 Что представляет собой последний десятичный разряд числа 74обо) а) 72о = 1 (шо41 25); б) 72 в— з 1 (пюб 4); в) 72о = 1 (пюг) 4); г) 7го 1 (пюб 100).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
