Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 81
Текст из файла (страница 81)
Через четыре года после возвращения Эйлер ослеп на второй глаз и оставался слепым последние !7 лет своей жизни, однако занятий математикой не прекращал. В 1771 году в доме Эйлера случился пожар. Его слуга-швейцарец, Петр Гримм, храбро ринулся в пылающий дом и вынес слепого Эйлера. Императрица Екатерина вскоре выстроила Эйлеру новый дом. Говорят, что 18 сентября 1783 года, проведя вечер за вычислением законов для описания подъема воздушных шаров и наметив в обших чертах вычисление орбиты открытой незадолго до того планеты Уран, Эйлер курил трубку и играл со своим внуком, когда его хватил удар.
Трубка вывалилась изо рта, он произнес слова: "Я умираю", и эпоха Эйлера закончилась. Сушествует целый ряд занимательных историй об Эйлере. Говорят, он мог декламировать слово в слово Энеиду Вергилия, хотя читал ее лишь в детстве. Тьебо (Тп1еЬац11) рассказывает, что к Российскому двору был пригашен Дидро, который, будучи атеистом, стал распространять свои идеи. Чтобы заставить его замолчать, был придуман план. Эйлер, истинно верующий христианин, подошел к Дидро и провозгласил по-французски: "(а + Ь™)(п = х, следовательно, Бог существует! Отвечайр' Дидро не знал математики, поэтому молчал. Поднялся хохот, отчего Дидро смутился настолько, что немедленно вернулся во Францию. РАадел 10.5.
порядок целого числе 439 Другая история повествует о том, как Эйлер, будучи в почтенном возрасте, слепой, был приглашен княгиней Дашковой посетить ее выступление в связи со вступлением княгини в должность директора Императорской Академии наук в Санкт-Петербурге. Эйлер, в сопровождении сына и внука, приехал вместе с княгиней в ее экипаже. После выступления, в котором Эйлеру была воздана высокая хвала, княгиня села на место, предполагая, что Эйлер займет почетное место рядом с ней. Высокомерный профессор Штелин занял это место до того, как Эйлера к нему подвели, Дашкова обратилась к Эйлеру с предложением занять любое место, сделав его тем самым почетным. Этот жест княгини произвел благоприятное впечатление на всех присутствовавших.
° УПРАЖНЕНИЯ 1. Найдите такие целые положительных числа т и п, что ф(тп) ф ф(т)ф(п). 2. Докажите, что если число р — простое и р > 2, то (р — 2)! = 1 (глоб р). 3. Докажите, что 1 2 3 . 1007 = 1 (той 1009). 4. Пусть (и — 1)! + 11 Б(п) = в1п Покажите, что число и — простое тогда и только тогда, когда о(п) = О. Б. Докажите теорему 10.23. 6.
Постройте таблицу значений ф(п) при 1 < п < 50. Т. Вычислите значение ф(2025). 8. Докажите, что если число п — составное и и > 4, то (и — 1)! = 0 (пюй и). 9. Докажите, что число и — простое тогда и только тогда, когда и делит (и — 1)! + 1. 10.5. ПОРЯДОК ЦЕЛОГО ЧИСЛА В этом разделе будут рассмотрены такие целые числа 1', что ад = 1 (гной гп).
В частности, нас будет интересовать наименьшее из этих положительных чисел Г'. ТЕОРЕМА 10.28. (Эйлер) Если гп — целое положительное число и НОД(а, гп) =1, то аеб'0 = 1 (глоб гп). ДОКАЗАТЕЛЬСТВО. Пусть т — целое положительное число и а — число, взаимно простое с пт. Если (хм ха,...,хь) — приведенная система вычетов по модулю гп, то, поскольку числа а и гп — взаимно простые, (ахы аха,...,ахь) также является системой приведенных вычетов. Следовательно, каждое х; сравнимо по модулю т только с одним ах .
Поэтому хгхз . хь са ах1ахз ..ахь (той гп) или а хгхз хь = хгхз хь (пюг1 т), и, поскольку числа т и х,хз . хь взаимно просты, то на х, можно сокрашать, что дает ааб"~ =— 1 (гпос1 гп). 440 ГПКВА 10. Некоторые специальные вопросы теории чисел Например, при а = 3, тп = 4 имеем ф(4) = 2, так что Зз = 9 = 1 (шог! 4). Если в теореме 10.28 гп — простое число, то каждое целое положительное число, которое меньше гп, является взаимно простым с гп, так что ф(т) = гп— 1.
Случай простого числа гл рассмотрен как следствие к теореме !0.20. Таким образом, как частный случай, справедлива следующая теорема. ТЕОРЕМА 10.29. (Малая теорема Ферма) Если р — простое число, то для каждого такого целого числа а, что 0 < а < р, имеем а" ': — 1 (пюб! р).
Например, если р = 7, то р — 1 = 6. В таком случае шестая степень каждого целого положительного числа, которое меньше р = 7, должна быть сравнима с 1 по модулю 7: 1 б 2 б 3б— 4 1 ь— а 1 (гпог! 7), 64 ь— а 1 (гпог) 7), 729 вз 1 (пюб) 7), 4096 = 1 (пюб 7), 15625 = 1 (пюг) 7), 46656 = 1 (глоб 7), 117649 = 0 (пюб 7). 5 6 б 7б— ОПРЕДЕЛЕНИЕ 10.30. Пусть п — целое положительное число и а — целое число такое, что НОД(а,п) = 1. Порядком числа а по модулю п называется наименьшее целое положительное число )с такое, что а" = 1 (пюг! п).
Это число обозначается через огг)„ а. ТЕОРЕМА 10.31. Пусть п — целое положительное число, НОД(а,п) = 1 и к = огг)„а. Тогда а) если а = 1 (пюд и), где т — целое положительное число, то Й ! тп; б) /с ) ф(п); в) для целых т и б, а' = а' (шог! и) тогда и только тогда, когда г в— з б (гпог! Й); Утверждение, обратное малой теореме Ферма, неверно. Например, Збб = 1 (пюг! 91) однако, 91 = 7. 13 — составное число. С другой стороны, если р — целое положительное число и 0 < а < р таково, что ае г ~ 1 (шоб р), тогда р не может быть простым. Таким образом, малая теорема Ферма содержит частичный критерий простоты числа, поскольку с ее помощью можно показать, что целое положительное число не является простым без определения нетривиального делителя числа р. Составные положительные числа и таковы, что а" = 1 (глоб и) для некоторого а, 1 < а < п, до определенной степени схожи с простыми числами; по атой причине такого рода составное число п называют псевдолростим числом по основанию а.
Таким образом, число и = 91 — псевдопростое по основанию а = 3. Однако, если выбрать а = 2, то получим 2бо = 64 ф 1 (пюг) 91); то есть, число п = 91 не является псевдопростым по основанию 2. Итак, 91 — псевдопростое число по основанию 3, но не является псевдопростым по основанию 2. РА311ЕЛ тд.д. Порядок цапово числа 441 а) Если а ь— э 1 (гной п) для целого положительного числа гн, то согласно алгоритму деления т = гс9+ г, где 0 < г < )с. Следовательно, а = а~с~" = а"са", так что а" = 1 (пюй п). Но это противоречит определению порядка числа а, если не г = О. Следовательно, к [ т.
б) Поскольку по теореме 10.28 имеем аВ~") = 1 (пюй п), из части (а) следует, что Й ] ф(п). в) Предположим, что г ) а. Поскольку числа а и и — взаимно простые, а' = а' (пюй и) тогда и только тогда, когда а" ' = 1 (пзой и); следовательно, согласно части (а) Й делит г — з, и г = з (пюй Й). г) Справедливость утверждения непосредственно следует из части (в). д) Пусть й = НОД(к, т), так что к = пй и гп = ий.
(а™т) "г нод(ь ™) = (а'")""~" = а" = а""" = а~"к>" = а"" = 1 (той и). Допустим, что число г таково, что (а™)' = 1 (пюй и). Тогда а ' = 1 (пюс1 п), так что )с [ т1, потому что огй„а = )с. Следовательно, ий [ ийс и, поскольку числа и и и — взаимно простые, и [ г. В силу того, что 1с = ий, ()с/й) = к/НОД,(к,т) делит г, поэтому к/НОД(к,т) и является порядком числа а по определению.
е) Это утверждение следует непосредственно из части (д). ПРИМЕР 10.32. Для иллюстрации теоремы !0.31 предположим, что и = 14 = 2.7, так что ф(п) = (2 — 1)(7 — 1) = 6. Первичная приведенная система вычетов для и = 14 есть множество (1,3,5,9,11,13). Рассмотрим приведенную ниже таблицу вычетов для степеней числа а = 5, [[а ]]„ [[а™]] „ 5 11 13 9 3 1 5 11 13 9 3 1 5 8 9 10 11 12 13 из которой видно, что после гп = 6 идет повторение одной и той образом, к = огс1ы 5 = 6. Для гл = 12, а = 5'~— : 1 (втой согласуется с утверждением теоремы 10.31(а).
Также огйы 5 ] 6 [ 6 [теорема 10.31(б)]. Кроме того, 2 = 8 = 14 (пюс1 6) и 5з же схемы. Таким 14) и )с [ гп, что ф(14), поскольку = 5а =— 5ы: — 11 г) никакие два из целых чисел а,аз,аз,...,а" не являются сравнимыми по модулю )с; д) если гп — целое положительное число, то порядок числа а по модулю п й НОД(/с, т) е) порядок числа а по модулю и равен к тогда и только тогда, когда числа гп и и — взаимно простые. ДОКАЗАТЕЛЬСТВО. 442 ГЛЯ8Я 10. Некоторые специальные вопросы теории чисел (шог) 14) [теорема 10.3Цв)]. Согласно таблице никакие два из чисел 51, 5з, 5з, 5~, 5з и 5е не являются сравнимыми по модулю 14 [теорема !О.ЗЦг)].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
