Блейхут Р. - Быстрые алгоритмы цифровой обработки сигналов (1044113), страница 28
Текст из файла (страница 28)
Докаэательстга. Утверждение вытекает из теоремы 2.1.5, так кан группа 6, содержит ф (р) элементов. Следствие 5.1.6 (теорема Ферма). Ег и р прасаим, лга для, каждою а гылалнлгтся ригенстза а' ' = 1 (юой р), али, гкзигалетпла, аг .= а (той р). Дакитатгльстга является тривиальным следствием теоремы, Эйлера, так как ф (а) = р — ! для любого простого р, О Теорема Ферма является также простым следствием следующей теоремы Теорема 5.1.7.
Есга р гроота, та отлтитглено умножения па людулю р иглулггмг з.ымглты кольца 27(р) образуют цикличе. скую группу, порождаемую приггизгиглмм элементам и. Доказательства сразу вытекает из теоремы 5 6.2, которую мм. осгавлнем на конец главы. г Согласно теореме Эйлера, если а в р взаимно просты, та по. рядок элемента а делит ф (р), ио не обязательно равен ф (рк Следующая теорема дает более подробную информацию аб этом для случая р, равного степени простого числа Это весьма сложная сварена теории чисел, и ее доказательство занимает всю оствв.
айюсн часть настоящего раздела. Оно опирается на еще не доказанную теорему 5 1.7, что, однако, вс создаст порочного круга, гак «ак в доказательстве теоремы 5.1.7 не используется теорелы 53 .8. Прежде ~ем переходить к агой теореме, приведем два примера Пусть р — 9; тогда 6, = (1, 2, 4, 5, 7, 8). г!егко провери~ь, чго порядок элемента 2 равен 6.
так чга его можно использовать в зачастае образующей цинлической группы 6,, Пусть р (8. Тогда бм =- Н, 3, 5, 7, 9, 11, 13, 15). Пере- сирая вге элементы, можно убелиться, что наибольший наряда~с всех элементов равен 4 (Таким элементом порядка 4 явлается элемент 3 ) Следователвна, группа 6м не является цикли геской Так как н следующей теореме р равна степени простого числа — ф (р'") - р — р ' = рг ' (р — 1). Теорема 5.1.8. Пут пь ш а р ирастаег тогда: (!) Если р лемтна, та группа 6, яглштся циктчесюй и люггарфиой группе (и) Есги р . 2 и р Э-8, та грулиа 6 „, не яглэетсл цлкли- Ч Сьай и ЗаМиРфеа гРУЛПЕ хг Х хг (мц если р = 4, пю группа 6„изамарфна группе хэ. Джагителгстга.
Утверждение п. (нП) теоремы тривиальна, так как существуег только одна группа с дауна элементами. Докаагельство остальных утверждений теоремы разбивается на пять :патов. Рйаг 1 и шаг 2 содержат доказательство в. (1) Па шаге 1 гокааывается, чгэ для нечетного р вайдется элемент порядка р -'; из шаге 2 даказываетск, что для ггечетноаз р найдетси элемент г рядка р — !. Так как р" †' и(р — 1) взаимно просты, то произведение этих двух элементов янляетсн элементом порядка р ' (р — 1), что и !!оказывает п.
(1) теоремы. Доказательство п. (Н) теоремы дается шагами 3 и 4. На шаге 3 доказывается, чта если р = 2, то порядок каждого элеиента делит 2"' .". На шаге 4 доказывается, что найдется элемент порядка 2"-'. Начнем с доказательства на шаге О одного полезного соотношения. (йаг й. Для всех целмх »исел а и Ь и произвольной степени р аросгога числа р выполняется сравнение (а (- Ьр)' ш аг (шой р ).
Доказательство этага шага нроведсьг индукнией па т. Для ги = 1 утверждение проверяется непосредствеммой проверкой Предположим, что для некоторого щ справедливо \а+ Ьр) м а' (люб р ). Тогда для некоторого целого й (и+ Ьр)' = и -)-йр . Возведем зта выражение в р.ю степень: ((а+ Ьр)' ) — (а' -)- Ьр ), (а+Ьр)» .=а +рйр а» и» л-~~~ г(») Ь р'"пы "" Второй член справа, так же «вк н все члены суммы, делится на р Ь'! следовательно, (а+ Ьр)» ц а (шоб р ), так что утвержденае справедливо прн переходе от ш н щ -1- 1, что и завершает индукцию.
Шщ 1. Положим а утверждении шага О числа а и 6 равными 1. Тогда (!+ р)'" ж ! (»пой р"), тан что порядок элемента (1+ р) делнт р6-ЧПокажемтеперь, что прв нечетном р порядок этого элемента в точности равен р -', для чего докажем, что этот порядок не делит числа р - "". А именно, для завер шенка доказательства шаге 1 докажем, что если щ > 1, то (!+р) ы 1-)-р (жабр").
Непосредственно нроверяется справедливость утверждения для щ = 2. Предположим, что оно выполняется для некоторого яг. Тогда для некоторого Ь выполняется равенство (1+р)~ -" 1+р +яр Следовательно, — ! (!+р)' = !+у(р 'шйр )+~ (п)(р" ' ';Ьр )'+ г з -)-(Р 1 "р ) Если р нечегно, то каждое из чнсел ( 1, ! ), ..., ) де. ы ы ~.-) лнтся на р. Каждый член в сумме делится по меньшей мере на рз "-пь, н.
едва ьно, делятся на р е! прн щ > 2. По- 1тз следннй член в правой часты равенства делится на р»' ", а, следовательно, прн р > 3 н щ > 2 делится на р"ч'. (Заметем, что доказательство не проходят при р .- 2.) Сясдовательна, порядок элемента (! -т- р) (пюб р ) не делнт р'"-А Это завершает доказательство топ», что порядок элемента (! -,'- р) равен р'"-С Шаз 2. Так как группа О,„ содержит р" -'(р — !) элементов, то порядок каждого ее элемента делят р -'(р — !).
Чтобы найти элемент группм порядка (р — П (пюб р ), выберем п равным примитввному элементу кольца х)(р) Тогда порздок и равен (р — 1) (шоб р). Покажем, что и — — к' .представляет собой искомый элемент порндка (р — 1) (шоб р ). Тзк как ч' — 1, то порядок элемента п должен делить р — 1; поэтому надо только поназшь, что порядок элемента и нс меньше, чем р — 1.
Так как и примитивен в кольце х)О»), то р — 1 гипеией и' для г = О, ..., р — 2, могут быть записаны в виде целых чисел .— а, -1- Ьгр, где а, пробегает все различные ненулевые целые числа, не преаосходюцне р — 1. Следовательно, используя шаг О, имеем (я)~, — (а,+Ьгр) —. ог (шобр ), нлн — (шоб р'"), где аг пробегает все различные ненулевые целые числа, не превосходящие р — ! . Следовательно, если мы докажем, что для любых двух целых чисел и и Ь, не превосходящих р — 1, выпалнзется соотношение й Ф6» (люб р ), то отсюда следует, что порядок этемевта а балыяе, челг р — 2.
но а' = а для любого элемента кольца 2)О»), так что а' = и (пгаб р). Следовательно, если а» =-. Ь' (шаб р ) то, конечно, ..г а = Ь '(шоб р), в, таким образом, л — - Ь (нюб р), что противоречит предположению о том, что а н Ь разлнчные не превосхадящне р — 1 целые числа Следовательно, порядок эле.
мента а равен р — 1 я п. (Ц теоремы доказан. Ш г У. Г!арядок каждого элемента группы О, делит 2 -'. Чтобы доказать это, сначала докажем, что для любых целых л и Ь выполняется сравнение (а з-46)~ = а» (люб 2 ). Поскольку элементами группы йт являются только нечетные числа, то, полагая а — ~ ! и варьируя Ь,сразу получаем из этопг сравнения нужное утверждение. Сравнение доказывается индунцней. Для т = 2 оно прове- ряется непосредственно. Предположим, что ано справедливо для некоторого положительного целого т, [огда для некоторого целого Ь (а ъ 4Ь)г = а' -г- Ь2 и, следовательно, (о + 4Ь)з = (а + Ь2") =- а + йа 2 т' [- Ь 2г". Таким образом, (а)-4Ь) и а (шод2" г').
Шаг 4. Нам осталась найти элемент порндка 2 -' прн т гь 3. Покажем, что 3' тв 1 (шод 2 ), так что 3 должно быть зле. ментом порядка 2 -'. При т -- 3 зто утверждение провернется непосредственно. Доказательства утвержп ния при т Ьь 4 со. состоит в доказательстве сравнения [1ж2) !+2 '(шод2 ). Эта сравнение просто проверяется д.чя т = 4. Предположим, что оно справедливо для некоторого т ) 4. Тогда для иекоторога Ь (1+2) =-1+2" '+В2".
Следовательно, (1-г2) =(1+2 +Д2'") = =- 1+ 2" + 2" " + Ь2 ъ' + Ь2'" -, Ьг2 и, таким образом, так как т больше трех, (1 [-2)г ы — 1ф2 (пюд2 г'). Следовательно, при всех т ) 3 выполняется сравнение (1+2)' =. 1-)-2 ' (шод 2 ). Таким образом, порядок 3 (пюд 2 ) не делит 2 ', к, следава. тельна, он равен 2" †', что н завершает доказательство.С[ 5.2.
Конечные полю, основанные н«кольце целых чисел Имеется очень важная конструкция, позволяющая по задан. ному кольцу построить новое кольцо, называемое его фа«лоркольцам. В случае провзвольнога кольца построение его фзктор- ыг а гиз ! гт кольца опирается на смежные классм. В случае кольца целых чисел факторкольцо строится просто: оно представляет собой ан кольцо целых чисел по модулю д, с которым мы уже встреча лись р ее, и обозначается через 3/(д) (или, попсе кратка, 2,); в этом случае его называют кольпом вычетов Пусть д — положительное целое число Кольцом вычетов 2/(д) называетсн множество [О, 1, ..., д — !) с операциямн сложении и умножения, определяемыми равенствами а -[- Ь =- ф Д [а+Ы, Ь=К [ау[. Элементм, обознвченийе через (О, 1, ..., д — 1[, принадлежат иак 2, так н 3/(д).
Элементы «алым 2)(д) названы так же, кап по и и первые д элементов кольна 2. Дело вкуса, подрачумеват ь лн д имн те же самые математичесние объекты или некоторые другие объекты с теми же именами. Два элемента а н Ь кольце 2, отображаемые в один н тпг же элемент «ольиа 7)(д), называются сравнимыми па модулю д, и а =- Ь -1- тд для некоторого целого лг. Теораза 3.2.1. Кольцо вычетов «Кд) ггягтгя лог ч м. Докаэттелястео.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
