Мультипликативная группа кольца вычетов. Мультипликативная группа вычетов по модулю n Пусть некоторое число п представлено в виде произведения попарно взаимно простых чисел

Свойства

Экспонента группы

Порождающее множество

Невозможно разобрать выражение (Выполняемый файл texvc не найден; См. math/README - справку по настройке.): U(\mathbb{Z}/n\mathbb{Z}) - циклическая группа тогда и только тогда, когда Невозможно разобрать выражение (Выполняемый файл texvc не найден; См. math/README - справку по настройке.): \varphi(n)=\lambda(n). В случае циклической группы генератор называется первообразным корнем .

Пример

Приведённая система вычетов по модулю Невозможно разобрать выражение (Выполняемый файл texvc не найден; См. math/README - справку по настройке.): 10 состоит из Невозможно разобрать выражение (Выполняемый файл texvc не найден; См. math/README - справку по настройке.): 4 классов вычетов: Невозможно разобрать выражение (Выполняемый файл texvc не найден; См. math/README - справку по настройке.): _{10}, _{10}, _{10}, _{10} . Относительно определённого для классов вычетов умножения они образуют группу, причём Невозможно разобрать выражение (Выполняемый файл texvc и Невозможно разобрать выражение (Выполняемый файл texvc не найден; См. math/README - справку по настройке.): _{10} взаимно обратны (то есть Невозможно разобрать выражение (Выполняемый файл texvc не найден; См. math/README - справку по настройке.): _{10}{\cdot}_{10} = _{10} ), а Невозможно разобрать выражение (Выполняемый файл texvc не найден; См. math/README - справку по настройке.): _{10} и Невозможно разобрать выражение (Выполняемый файл texvc не найден; См. math/README - справку по настройке.): _{10} обратны сами себе.

Структура группы

Запись Невозможно разобрать выражение (Выполняемый файл texvc не найден; См. math/README - справку по настройке.): C_n означает «циклическая группа порядка n».

Применение

История

Вклад в исследование структуры мультипликативной группы кольца вычетов внесли Артин , Билхарц, Брауэр , Вильсон, Гаусс , Лагранж , Лемер, Уоринг , Ферма, Хули, Эйлер . Лагранж доказал лемму о том, что если Невозможно разобрать выражение (Выполняемый файл texvc не найден; См. math/README - справку по настройке.): f(x) \in k[x] , и k - поле, то f имеет не более n различных корней, где n - степень f. Он же доказал важное следствие этой леммы, заключающееся в сравнении Невозможно разобрать выражение (Выполняемый файл texvc не найден; См. math/README - справку по настройке.): x^{p-1}-1 ≡ Невозможно разобрать выражение (Выполняемый файл texvc не найден; См. math/README - справку по настройке.): (x-1)(x-2)...(x-p+1)mod(p) . Эйлер доказал малую теорему Ферма . Уоринг сформулировал теорему Вильсона, а Лагранж её доказал. Эйлер предположил существование примитивных корней по модулю простого числа. Гаусс это доказал. Артин выдвинул свою гипотезу о существовании и количественной оценке простых чисел, по модулю которых заданное целое число является первообразным корнем. Брауэр внес вклад в исследование проблемы существования наборов последовательных целых чисел, каждое из которых - k-ая степень по модулю p. Билхарц доказал аналог гипотезы Артина. Хули доказал гипотезу Артина с предположением справедливости расширенной гипотезы Римана в полях алгебраических чисел.

Напишите отзыв о статье "Мультипликативная группа кольца вычетов"

Примечания

Литература

• Айерлэнд К., Роузен М. Классическое введение в современную теорию чисел. - М .: Мир, 1987.
• Алферов А.П., Зубов А.Ю., Кузьмин А.С. Черемушкин А.В. Основы криптографии. - Москва: «Гелиос АРВ», 2002.
• Ростовцев А.Г., Маховенко Е.Б. Теоретическая криптография. - Санкт-Петербург: НПО «Профессионал», 2004.

Ссылки

• Бухштаб А. А. Теория чисел. - М .: Просвещение, 1966.
• Weisstein, Eric W. (англ.) на сайте Wolfram MathWorld .

Отрывок, характеризующий Мультипликативная группа кольца вычетов

Тела группа, элементами к рой являются все ненулевые элементы данного тела, а операция совпадает с операцией умножения в теле. М. г. поля абелева группа. О. А. Иванова … Математическая энциклопедия

Приведённая система вычетов по модулю m множество всех чисел полной системы вычетов по модулю m, взаимно простых с m. Приведённая система вычетов по модулю m состоит из φ(m) чисел, где φ(·) функция Эйлера. В качестве приведённой системы вычетов… … Википедия

Теория групп … Википедия

Группа в абстрактной алгебре непустое множество с определённой на нём бинарной операцией, удовлетворяющей указанным ниже аксиомам. Ветвь математики, занимающаяся группами, называется теорией групп. Всем знакомые вещественные числа наделены… … Википедия

Группа автоморфизмов нек рой полуторалинейной формы f на правом K модуле Е, где К кольцо; при этом f и Е(а иногда и К)удовлетворяют дополнительным условиям. Точного определения К. г. нет. Предполагается, что f либо нулевая, либо невырожденная… … Математическая энциклопедия

Группа всех обратимых матриц степени пнад ассоциативным кольцом K с единицей; общепринятое обозначение: GLn(K).или GL(n, К). П. л. г. GL(n, K) может быть также определена как группа автоморфизмов АutK(V) свободного правого K модуля Vс… … Математическая энциклопедия

Для общего описания теории групп см. Группа (математика) и Теория групп. Курсив обозначает ссылку на этот словарь. # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У … Википедия

По модулю m , которая обозначается $\backslash mathbb\{Z\}\_m^\{\backslash times\}$ или $U(\backslash mathbb\{Z\}\_m)$ .

Если m простое, то, как отмечалось выше, элементы 1, 2, ...,m -1 входят в $\backslash mathbb\{Z\}\_m^\{\backslash times\}$. В этом случае $\backslash mathbb\{Z\}\_m^\{\backslash times\}$ является полем .

Формы записи

Кольцо вычетов по модулю n обозначают $\backslash mathbb\{Z\}/n\backslash mathbb\{Z\}$ или $\backslash mathbb\{Z\}\_n$. Его мультипликативную группу, как и в общем случае групп обратимых элементов колец, обозначают $(\backslash mathbb\{Z\}/n\backslash mathbb\{Z\})^*,$ $(\backslash mathbb\{Z\}/n\backslash mathbb\{Z\})^\backslash times,$ $U(\backslash mathbb\{Z\}/n\backslash mathbb\{Z\}),$ $E(\backslash mathbb\{Z\}/n\backslash mathbb\{Z\}),$ $\backslash mathbb\{Z\}\_n^\{\backslash times\},$ $U(\backslash mathbb\{Z\}\_n)$.

Простейший случай

Чтобы понять структуру группы $U(\backslash mathbb\{Z\}/n\backslash mathbb\{Z\})$, можно рассмотреть частный случай $n=p^a$, где $p$ - простое число, и обобщить его. Рассмотрим простейший случай, когда $a=1$, т.е. $n=p$.

Теорема: $U(\backslash mathbb\{Z\}/p\backslash mathbb\{Z\})$ - циклическая группа.

Пример : Рассмотрим группу $U(\backslash mathbb\{Z\}/9\backslash mathbb\{Z\})$

$U(\backslash mathbb\{Z\}/9\backslash mathbb\{Z\})$ = {1,2,4,5,7,8} Генератором группы является число 2. $2^1\; \backslash equiv\; 2\backslash \; \backslash pmod\; 9$ $2^2\; \backslash equiv\; 4\backslash \; \backslash pmod\; 9$ $2^3\; \backslash equiv\; 8\backslash \; \backslash pmod\; 9$ $2^4\; \backslash equiv\; 7\backslash \; \backslash pmod\; 9$ $2^5\; \backslash equiv\; 5\backslash \; \backslash pmod\; 9$ $2^6\; \backslash equiv\; 1\backslash \; \backslash pmod\; 9$ Как видим, любой элемент группы $U(\backslash mathbb\{Z\}/9\backslash mathbb\{Z\})$ может быть представлен в виде $2^l$, где . То есть группа $U(\backslash mathbb\{Z\}/9\backslash mathbb\{Z\})$ - циклическая.

Общий случай

Для рассмотрения общего случая необходимо определение примитивного корня . Примитивный корень по простому модулю $p$ – это число, которое вместе со своим классом вычетов порождает группу $U(\backslash mathbb\{Z\}/p\backslash mathbb\{Z\})$.

В случае целого модуля $n$ определение такое же.

Структуру группы определяет следующая теорема: Если p - нечётное простое число и l – целое положительное, то существуют примитивные корни по модулю $p^\{l\}$, то есть $U(\backslash mathbb\{Z\}/p^\{l\}\backslash mathbb\{Z\})$ - циклическая группа.

Подгруппа свидетелей простоты

Пусть $m$ - нечётное число большее 1. Число $m-1$ однозначно представляется в виде $m-1\; =\; 2^s\; \backslash cdot\; t$, где $t$ нечётно. Целое число $a$, , называется свидетелем простоты числа $m$, если выполняется одно из условий:

• $a^t\backslash equiv\; 1\backslash pmod\; m$

• существует целое число $k$,

Если число $m$ - составное, существует подгруппа мультипликативной группы кольца вычетов, называемая подгруппой свидетелей простоты. Её элементы, возведённые в степень $m-1$, совпадают с $1$ по модулю $m$.

Пример : $m=9$. Есть $6$ остатков, взаимно простых с $9$, это $1,2,4,5,7$ и $8$. $8$ эквивалентно $-1$ по модулю $9$, значит $8^\{8\}$ эквивалентно $1$ по модулю $9$. Значит, $1$ и $8$ - свидетели простоты числа $9$. В данном случае {1, 8} - подгруппа свидетелей простоты.

Свойства

Экспонента группы

Порождающее множество

$U(\backslash mathbb\{Z\}/n\backslash mathbb\{Z\})$ - циклическая группа тогда и только тогда, когда $\backslash varphi(n)=\backslash lambda(n).$ В случае циклической группы генератор называется первообразным корнем .

Пример

Приведённая система вычетов по модулю $10$ состоит из $4$ классов вычетов: $\_\{10\},\; \_\{10\},\; \_\{10\},\; \_\{10\}$. Относительно определённого для классов вычетов умножения они образуют группу, причём $\_\{10\}$ и $\_\{10\}$ взаимно обратны (то есть $\_\{10\}\{\backslash cdot\}\_\{10\}\; =\; \_\{10\}$), а $\_\{10\}$ и $\_\{10\}$ обратны сами себе.

Структура группы

Запись $C\_n$ означает «циклическая группа порядка n».

Применение

История

Вклад в исследование структуры мультипликативной группы кольца вычетов внесли Артин , Билхарц, Брауэр , Вильсон, Гаусс , Лагранж , Лемер, Уоринг , Ферма, Хули, Эйлер . Лагранж доказал лемму о том, что если $f(x)\; \backslash in\; k[x]$, и k - поле, то f имеет не более n различных корней, где n - степень f. Он же доказал важное следствие этой леммы, заключающееся в сравнении $x^\{p-1\}-1$ ≡ $(x-1)(x-2)...(x-p+1)mod(p)$. Эйлер доказал малую теорему Ферма . Уоринг сформулировал теорему Вильсона, а Лагранж её доказал. Эйлер предположил существование примитивных корней по модулю простого числа. Гаусс это доказал. Артин выдвинул свою гипотезу о существовании и количественной оценке простых чисел, по модулю которых заданное целое число является первообразным корнем. Брауэр внес вклад в исследование проблемы существования наборов последовательных целых чисел, каждое из которых - k-ая степень по модулю p. Билхарц доказал аналог гипотезы Артина. Хули доказал гипотезу Артина с предположением справедливости расширенной гипотезы Римана в полях алгебраических чисел.

Напишите отзыв о статье "Мультипликативная группа кольца вычетов"

Примечания

Литература

• Айерлэнд К., Роузен М. Классическое введение в современную теорию чисел. - М .: Мир, 1987.
• Алферов А.П., Зубов А.Ю., Кузьмин А.С. Черемушкин А.В. Основы криптографии. - Москва: «Гелиос АРВ», 2002.
• Ростовцев А.Г., Маховенко Е.Б. Теоретическая криптография. - Санкт-Петербург: НПО «Профессионал», 2004.

Ссылки

• Бухштаб А. А. Теория чисел. - М .: Просвещение, 1966.
• Weisstein, Eric W. (англ.) на сайте Wolfram MathWorld .

Отрывок, характеризующий Мультипликативная группа кольца вычетов

– Ma bonne amie, [Мой добрый друг,] – сказала маленькая княгиня утром 19 го марта после завтрака, и губка ее с усиками поднялась по старой привычке; но как и во всех не только улыбках, но звуках речей, даже походках в этом доме со дня получения страшного известия была печаль, то и теперь улыбка маленькой княгини, поддавшейся общему настроению, хотя и не знавшей его причины, – была такая, что она еще более напоминала об общей печали.
– Ma bonne amie, je crains que le fruschtique (comme dit Фока – повар) de ce matin ne m"aie pas fait du mal. [Дружочек, боюсь, чтоб от нынешнего фриштика (как называет его повар Фока) мне не было дурно.]
– А что с тобой, моя душа? Ты бледна. Ах, ты очень бледна, – испуганно сказала княжна Марья, своими тяжелыми, мягкими шагами подбегая к невестке.
– Ваше сиятельство, не послать ли за Марьей Богдановной? – сказала одна из бывших тут горничных. (Марья Богдановна была акушерка из уездного города, жившая в Лысых Горах уже другую неделю.)
– И в самом деле, – подхватила княжна Марья, – может быть, точно. Я пойду. Courage, mon ange! [Не бойся, мой ангел.] Она поцеловала Лизу и хотела выйти из комнаты.
– Ах, нет, нет! – И кроме бледности, на лице маленькой княгини выразился детский страх неотвратимого физического страдания.
– Non, c"est l"estomac… dites que c"est l"estomac, dites, Marie, dites…, [Нет это желудок… скажи, Маша, что это желудок…] – и княгиня заплакала детски страдальчески, капризно и даже несколько притворно, ломая свои маленькие ручки. Княжна выбежала из комнаты за Марьей Богдановной.
– Mon Dieu! Mon Dieu! [Боже мой! Боже мой!] Oh! – слышала она сзади себя.
Потирая полные, небольшие, белые руки, ей навстречу, с значительно спокойным лицом, уже шла акушерка.
– Марья Богдановна! Кажется началось, – сказала княжна Марья, испуганно раскрытыми глазами глядя на бабушку.
– Ну и слава Богу, княжна, – не прибавляя шага, сказала Марья Богдановна. – Вам девицам про это знать не следует.
– Но как же из Москвы доктор еще не приехал? – сказала княжна. (По желанию Лизы и князя Андрея к сроку было послано в Москву за акушером, и его ждали каждую минуту.)
– Ничего, княжна, не беспокойтесь, – сказала Марья Богдановна, – и без доктора всё хорошо будет.
Через пять минут княжна из своей комнаты услыхала, что несут что то тяжелое. Она выглянула – официанты несли для чего то в спальню кожаный диван, стоявший в кабинете князя Андрея. На лицах несших людей было что то торжественное и тихое.
Княжна Марья сидела одна в своей комнате, прислушиваясь к звукам дома, изредка отворяя дверь, когда проходили мимо, и приглядываясь к тому, что происходило в коридоре. Несколько женщин тихими шагами проходили туда и оттуда, оглядывались на княжну и отворачивались от нее. Она не смела спрашивать, затворяла дверь, возвращалась к себе, и то садилась в свое кресло, то бралась за молитвенник, то становилась на колена пред киотом. К несчастию и удивлению своему, она чувствовала, что молитва не утишала ее волнения. Вдруг дверь ее комнаты тихо отворилась и на пороге ее показалась повязанная платком ее старая няня Прасковья Савишна, почти никогда, вследствие запрещения князя,не входившая к ней в комнату.
– С тобой, Машенька, пришла посидеть, – сказала няня, – да вот княжовы свечи венчальные перед угодником зажечь принесла, мой ангел, – сказала она вздохнув.
– Ах как я рада, няня.
– Бог милостив, голубка. – Няня зажгла перед киотом обвитые золотом свечи и с чулком села у двери. Княжна Марья взяла книгу и стала читать. Только когда слышались шаги или голоса, княжна испуганно, вопросительно, а няня успокоительно смотрели друг на друга. Во всех концах дома было разлито и владело всеми то же чувство, которое испытывала княжна Марья, сидя в своей комнате. По поверью, что чем меньше людей знает о страданиях родильницы, тем меньше она страдает, все старались притвориться незнающими; никто не говорил об этом, но во всех людях, кроме обычной степенности и почтительности хороших манер, царствовавших в доме князя, видна была одна какая то общая забота, смягченность сердца и сознание чего то великого, непостижимого, совершающегося в эту минуту.
В большой девичьей не слышно было смеха. В официантской все люди сидели и молчали, на готове чего то. На дворне жгли лучины и свечи и не спали. Старый князь, ступая на пятку, ходил по кабинету и послал Тихона к Марье Богдановне спросить: что? – Только скажи: князь приказал спросить что? и приди скажи, что она скажет.
– Доложи князю, что роды начались, – сказала Марья Богдановна, значительно посмотрев на посланного. Тихон пошел и доложил князю.
– Хорошо, – сказал князь, затворяя за собою дверь, и Тихон не слыхал более ни малейшего звука в кабинете. Немного погодя, Тихон вошел в кабинет, как будто для того, чтобы поправить свечи. Увидав, что князь лежал на диване, Тихон посмотрел на князя, на его расстроенное лицо, покачал головой, молча приблизился к нему и, поцеловав его в плечо, вышел, не поправив свечей и не сказав, зачем он приходил. Таинство торжественнейшее в мире продолжало совершаться. Прошел вечер, наступила ночь. И чувство ожидания и смягчения сердечного перед непостижимым не падало, а возвышалось. Никто не спал.

Была одна из тех мартовских ночей, когда зима как будто хочет взять свое и высыпает с отчаянной злобой свои последние снега и бураны. Навстречу немца доктора из Москвы, которого ждали каждую минуту и за которым была выслана подстава на большую дорогу, к повороту на проселок, были высланы верховые с фонарями, чтобы проводить его по ухабам и зажорам.
Княжна Марья уже давно оставила книгу: она сидела молча, устремив лучистые глаза на сморщенное, до малейших подробностей знакомое, лицо няни: на прядку седых волос, выбившуюся из под платка, на висящий мешочек кожи под подбородком.
Няня Савишна, с чулком в руках, тихим голосом рассказывала, сама не слыша и не понимая своих слов, сотни раз рассказанное о том, как покойница княгиня в Кишиневе рожала княжну Марью, с крестьянской бабой молдаванкой, вместо бабушки.
– Бог помилует, никогда дохтура не нужны, – говорила она. Вдруг порыв ветра налег на одну из выставленных рам комнаты (по воле князя всегда с жаворонками выставлялось по одной раме в каждой комнате) и, отбив плохо задвинутую задвижку, затрепал штофной гардиной, и пахнув холодом, снегом, задул свечу. Княжна Марья вздрогнула; няня, положив чулок, подошла к окну и высунувшись стала ловить откинутую раму. Холодный ветер трепал концами ее платка и седыми, выбившимися прядями волос.
– Княжна, матушка, едут по прешпекту кто то! – сказала она, держа раму и не затворяя ее. – С фонарями, должно, дохтур…
– Ах Боже мой! Слава Богу! – сказала княжна Марья, – надо пойти встретить его: он не знает по русски.
Княжна Марья накинула шаль и побежала навстречу ехавшим. Когда она проходила переднюю, она в окно видела, что какой то экипаж и фонари стояли у подъезда. Она вышла на лестницу. На столбике перил стояла сальная свеча и текла от ветра. Официант Филипп, с испуганным лицом и с другой свечей в руке, стоял ниже, на первой площадке лестницы. Еще пониже, за поворотом, по лестнице, слышны были подвигавшиеся шаги в теплых сапогах. И какой то знакомый, как показалось княжне Марье, голос, говорил что то.

Теорема 7.

Доказательство.

В дальнейшем мы для простоты будем обозначать сложение и умножение по модулю обычными знаками + и ∙ (иногда опуская знак умножения), а аддит

5) Количество обратимых элементов в кольце вычетов.

Можно доказать такую формулу для функции Эйлера: (3) где p1,….,ps – список всех простых делителей числа n. Можно пояснить эту формулу так: случа

6) Подгруппы.

10. Если является подгруппой конечной группы, то делит.

11. Доказательство.

12. Следствие 8.1.

13. 7) Подгруппа, порожденная элементом группы.

14. Если группа S конечна, то последовательность будет периодической (следующий элемент определяется предыдущим, поэтому раз повторившись, эл

15. Указанные t элементов образуют подгруппу, т.к. групповая операция соответствует сложению «показателей степени». Эта подгруппа называется

16. Вот несколько подгрупп группы Z6 , порожденных различными элементами: . Аналогичный пример для мультипликативной группы: здесь Из сказанно

17. Пусть - конечная группа. Если, то число элементов в подгруппе, порождаемой а, совпадает с порядком а (т.е.).

18. Следствие 9.1.

19. Следствие 9.2.

20. 8) Решение линейных диофантовых уравнений.

21. Напомним, что через обозначается порождённая элементом а подгруппа (в данном случае подгруппа группы Zn). По определению, поэтому уравнени

22. Пусть уравнение разрешимо и является его решением. Тогда уравнение имеет d =НОД(а,n) решений в Zn , задаваемых формулой, где i = 0,1,2,... , n - 1.

23. Доказательство.

24. Пусть n > 1. Если НОД(а, n) = 1, то уравнение имеет единственное решение (в Zn). Случай b=1 особенно важен – при этом мы находим обратный к х элемент п

25. Следствие 10.2

26. 9) Китайская теорема об остатках.

27. Пусть некоторое число п представлено в виде произведения попарно взаимно простых чисел. Китайская теорема об остатках утверждает, что кол

28. 10) Степени элемента.

29. 11) Теорема 11 (Эйлер).

30. 12) Теорема 12 (малая теорема Ферма).

31. Следствие 12.1. Пусть p – простое число Следствие 12.2. Пусть p – простое число, тогда теорема Ферма будет применима и к а=0.

32. 13) Теорема 13 (Усиление теоремы Эйлера).

33. ч.т.д.

34. 14) Вычисление степеней повторным возведением в квадрат.

35. Пусть мы хотим вычислить ab mod n, где а – вычет по модулю n, a b – целое неотрицательное число, имеющее в двоичной записи вид (bk,bk-1,... ,b1,b0) (число з

36. При умножении с на 2 число ас возводится в квадрат, при увеличении с на 1 число ас умножается на a. На каждом шаге двоичная запись с сдвигается

37. Оценим время работы процедуры. Если три числа, являющиеся её исходными данными, имеют не более β битов, то число арифметических операций ес

38.