Согласно свойству сравнений №15, числа одного и того же класса по модулю m имеют с модулем m один и тот же НОД. Особенно важны классы, для которых он равен 1.
Взяв от каждого из таких классов по одному числу, получим приведенную систему вычетов по модулю m . Обычно ее выделяют из системы наименьших неотрицательных вычетов по модулю m .
Приведенная система наименьших неотрицательных вычетов по модулю m обозначается U m .
Количество чисел в приведенной системе вычетов по модулю m , очевидно, равно φ(m ).
Пример :
Приведенная система вычетов по модулю 15 есть {1; 2; 4; 7; 8; 11; 13; 14}. Заметим, что φ(15)=(5–1)∙(3–1)= 8 и действительно, в приведенной системе вычетов по модулю 15 ровно 8 элементов.
Утверждение 1
Любые φ(m ) чисел, попарно несравнимых по модулю m и взаимно простых с m , образуют приведенную систему вычетов.
(Доказательство очевидно как в утверждении 1 пункт 2)
Утверждение 2
Если (a , m ) = 1, x пробегает приведенную систему вычетов по модулю m , то ax тоже пробегает приведенную систему вычетов по модулю m . (Доказательство очевидно как в утверждении 2 пункт 2).
Обратный элемент.
Говорят, что элемент b называется обратным к a по модулю m , если a∙b ≡1(mod m ), и пишут b ≡ a –1 (mod m ).
Вообще, классическая теория чисел не нуждается в таком понятии как обратный элемент, в чем можно убедиться, ознакомившись, например, с . Однако криптология использует системы вычетов как в теоретико-числовом, так и в алгебраическом аспекте, а потому, для удобства изложения алгебраических основ криптологии, мы вводим понятие обратного элемента.
Возникает вопрос – для всех ли элементов по данному модулю m существует обратный (по умножению), и если для каких-то элементов обратный существует, как его найти?
Для ответа на этот вопрос воспользуемся расширенным алгоритмом Евклида. Рассмотрим сначала взаимно простые число a и модуль m . Тогда, очевидно, (a ,m )=1. Расширенный алгоритм Евклида позволяет получить числа x и y , такие, что ax+my= (a ,m ), или, что то же самое, ax+my =1. Из последнего выражения получаем сравнение ax+my ≡1(mod m ). Поскольку my ≡0(mod m ), то ax ≡1(mod m ), а значит полученное с помощью расширенного алгоритма Евклида число x как раз и есть искомый обратный элемент к числу a по модулю m .
Пример.
a =5, m =7. Требуется найти a -1 mod m .
Воспользуемся расширенным алгоритмом Евклида.
Обратный ход:
1=5–2∙2=5–(7–5∙1)∙2=5∙3–7∙2.
x =3, y =–2.
5 -1 ≡3(mod 7)
Проверка: 5∙3=15. 15≡1(mod 7).
Действительно, 3 является обратным элементом к 5 по модулю 7.
Итак, конструктивным образом убедились в том, что для чисел, взаимно простых с модулем, существует обратный по этому модулю. А существуют ли обратные элементы для чисел, не являющихся с модулем взаимно простыми?
Пусть (a ,m )=d ≠1. Тогда a и m представимы в виде a =d ∙a 1 , m =d ∙m 1 . Допустим, что для a существует обратный элемент по модулю m, то есть b : a ∙b ≡1(modm ). Тогда a ∙b= m ∙k +1. Или, что то же самое, d ∙a 1 ∙b= d ∙m 1 ∙k +1. Но тогда по теореме 2 из §1 п.1, в силу того, что и левая часть данного уравнения, и первое слагаемое в правой части делятся на d , то d \1, а это не так, поскольку d ≠1. Пришли к противоречию, следовательно предположение о существовании обратного элемента неверно.
m - набор, составленный из всех чисел полной системы вычетов по модулю m , взаимно простых с m . Приведённая система вычетов по модулю m состоит из φ(m ) чисел, где φ(m ) - функция Эйлера . В качестве приведённой системы вычетов по модулю m обычно берутся взаимно простые с m числа от 0 до m - 1 .Wikimedia Foundation . 2010 .
- Drag-and-drop
- 2С25 «Спрут-СД»
Смотреть что такое "Приведённая система вычетов" в других словарях:
Приведённая система вычетов - часть полной системы вычетов (См. Полная система вычетов), состоящая из чисел взаимно простых с модулем m. П. с. в. содержит φ(m) чисел [φ(m) число чисел, взаимно простых с m и меньших m]. Всякие φ(m) чисел, не сравнимые по модулю m и… … Большая советская энциклопедия
Приведенная система вычетов - Приведённая система вычетов по модулю m набор, составленный из всех чисел полной системы вычетов по модулю m, взаимно простых с m. Приведённая система вычетов по модулю m состоит из φ(m) чисел, где φ(m) функция Эйлера. В качестве приведённой… … Википедия
Мультипликативная группа кольца вычетов - Приведённая система вычетов по модулю m множество всех чисел полной системы вычетов по модулю m, взаимно простых с m. Приведённая система вычетов по модулю m состоит из φ(m) чисел, где φ(·) функция Эйлера. В качестве приведённой системы вычетов… … Википедия
Функция Эйлера - Не следует путать с функцией распределения простых чисел. Первая тысяча значений Функция Эйлера φ(n) мультипликативная … Википедия
Сравнение по модулю - Сравнение по модулю натурального числа n в теории чисел отношение эквивалентности на кольце целых чисел, связанное с делимостью на n. Факторкольцо по этому отношению называется кольцом вычетов. Совокупность соответствующих тождеств и… … Википедия
Конечная группа - Симметрия снежинки связана с группой поворотов на угол, кратный 60° Конечная группа алгебраическая группа, содержащая конечное число элементов (это число называется её порядком). Далее группа предполагается мультипликативной, то есть операция в… … Википедия
Четверная группа Клейна - Четверная группа Клейна группа четвёртого порядка, играет важную роль в высшей алгебре. Содержание 1 Определение 2 Обозначение 3 … Википедия
В предыдущем пункте было отмечено, что отношение m сравнимости по произвольному модулю m есть отношение эквивалентности на множестве целых чисел. Это отношение эквивалентности индуцирует разбиение множества целых чисел на классы эквивалентных между собой элементов, т.е. в один класс объединяются числа, дающие при делении на m одинаковые остатки. Число классов эквивалентности m (знатоки скажут – "индекс эквивалентности m ") в точности равно m .
Определение. Любое число из класса эквивалентности m будем называть вычетом по модулю m . Совокупность вычетов, взятых по одному из каждого класса эквивалентности m , называется полной системой вычетов по модулю m (в полной системе вычетов, таким образом, всего m штук чисел). Непосредственно сами остатки при делении на m называются наименьшими неотрицательными вычетами и, конечно, образуют полную систему вычетов по модулю m . Вычет ρ называется абсолютно наименьшим, если ⎪ρ ⎪ наименьший среди модулей вычетов данного класса.
Пример : Пусть m = 5. Тогда:
0, 1, 2, 3, 4 - наименьшие неотрицательные вычеты;
2, -1, 0, 1, 2 - абсолютно наименьшие вычеты.
Обе приведенные совокупности чисел образуют полные системы вычетов по модулю 5.
Лемма 1 . 1) Любые m штук попарно не сравнимых по модулю m чисел образуют полную систему вычетов по модулю m .
2) Если а и m взаимно просты, а x пробегает полную систему вычетов по модулю m , то значения линейной формы а x + b , где b – любое целое число, тоже пробегают полную систему вычетов по модулю m .
Доказательство. Утверждение 1) – очевидно. Докажем утверждение 2) Чисел а x +b ровно m штук. Покажем, что они между собой не сравнимы по модулю m . Ну пусть для некоторых различных x 1 и x 2 из полной системы вычетов оказалось, что ax 1 + b ≡ ax 2 + b (mod m). Тогда, по свойствам сравнений из предыдущего пункта, получаем:
ax 1 ≡ ax 2 (mod m )
x 1 ≡ x 2 (mod m )
– противоречие с тем, что x 1 и x 2 различны и взяты из полной системы вычетов.
Поскольку все числа из данного класса эквивалентности m получаются из одного числа данного класса прибавлением числа, кратного m , то все числа из данного класса имеют с модулем m один и тот же наибольший общий делитель. По некоторым соображениям, повышенный интерес представляют те вычеты, которые имеют с модулем m наибольший общий делитель, равный единице, т.е. вычеты, которые взаимно просты с модулем.
Определение. Приведенной системой вычетов по модулю m называется совокупность всех вычетов из полной системы, взаимно простых с модулем m .
Приведенную систему обычно выбирают из наименьших неотрицательных вычетов. Ясно, что приведенная система вычетов по модулю m содержит ϕ (m ) штук вычетов, где ϕ (m )– функция Эйлера – число чисел, меньших m и взаимно простых с m .
Функция Эйлера.
Функция Эйлера ϕ (a ) есть количество чисел из ряда 0, 1, 2,..., a –1, взаимно простых с a .
Лемма. Пусть
Т
огда:
в частности, φ(p α) = p α –p α -1 , φ(p ) = p –1.
Пример . Пусть m = 42. Тогда приведенная система вычетов суть:
1, 5, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41.
Лемма 2. 1) Любые ϕ (m ) чисел, попарно не сравнимые по модулю m и взаимно простые с модулем, образуют приведенную систему вычетов по модулю m .
2) Если d (a , m ) = 1 и x пробегает приведенную систему вычетов по модулю m , то а x так же пробегает приведенную систему вычетов по модулю m .
Доказательство . Утверждение 1) – очевидно. Докажем утверждение 2). Числа а x попарно несравнимы (это доказывается так же, как в лемме 1 этого пункта), их ровно ϕ (m ) штук. Ясно также, что все они взаимно просты с модулем, ибо d (a , m )=1, d (x ,m )=1 ⇒ d (ax , m )=1. Значит, числа а x образуют приведенную систему вычетов.
Лемма 3. Пусть m 1 , m 2 , ..., m k – попарно взаимно просты и m 1 m 2 ...m k =M 1 m 1 =M 2 m 2 =...=M k m k , где M j =m 1 ...m j -1 m j +1 ...m k
1) Если x 1 , x 2 , ..., x k пробегают полные системы вычетов по модулям m 1 , m 2 , ..., m k M 1 x 1 +M 2 x 2 + ...+M k x k пробегают полную систему вычетов по модулю m= m 1 m 2 ...m k .
2) Если ξ 1 , ξ 2 , ..., ξ k пробегают приведенные системы вычетов по модулям m 1 , m 2 , ..., m k соответственно, то значения линейной формы M 1 ξ 1 +M 2 ξ 2 + ...+M k ξ k пробегают приведенную систему вычетов по модулю m= m 1 m 2 ...m k .
Лемма 4. Пусть x 1 , x 2 , ..., x k , x пробегают полные, а ξ 1 , ξ 2 ,..., ξ k , ξ – пробегают приведенные системы вычетов по модулям m 1 , m 2 ,...,m k и m=m 1 m 2 ...m k соответственно, где (m i m j )=1 при i ≠ j . Тогда дроби {x 1 /m 1 +x 2 /m 2 +...+x k /m k } совпадают с дробями {x/m} , а дроби { ξ 1 /m 1 + ξ 2 /m 2 +...+ ξ k /m k } совпадают с дробями { ξ/m} .
Обозначим через ε k k -ый корень m- ой степени из единицы:
Здесь k =0,1,...,m -1 – пробегает полную систему вычетов по модулю m .
Напомню, что сумма ε 0 + ε 1 +...+ ε m-1 всех корней m -ой степени из единицы равна нулю для любого m . Действительно, пусть ε 0 + ε 1 +...+ ε m-1 = a . Умножим эту сумму на ненулевое число ε 1 . Такое умножение геометрически в комплексной плоскости означает поворот правильного m -угольника, в вершинах которого расположены корни ε 0 + ε 1 +...+ ε m-1 , на ненулевой угол 2 π/m . Ясно, что при этом корень ε 0 перейдет в корень ε 1 , корень ε 1 перейдет в корень ε 2 , и т.д., а корень ε m-1 перейдет в корень ε 0 , т.е. сумма ε 0 + ε 1 +...+ ε m-1 не изменится. Имеем ε 1 a=a , откуда a=0 .
Теорема 1. Пусть m>0 – целое число, a Z , x пробегает полную систему вычетов по модулю m . Тогда, если а кратно m , то
в противном случае, при а не кратном m ,
Теорема 2. Пусть m>0 – целое число, ξ пробегает приведенную систему вычетов по модулю m . Тогда (сумма первообразных корней степени m ):
где μ(m ) – функция Мебиуса.
или же любые последовательные p числа.
Данная система называется полною системою чисел, не сравнимых по модулю p или же полною системою вычетов по модулю p . Очевидно, что всякие p последовательных чисел образуют такую систему.
Все числа, принадлежащих к одному классу, имеют много общих свойств, следовательно по отношению к модулю их можно рассматривать как одно число. Каждое число, входящее в сравнение как слагаемое или множитель, может быть заменено, без нарушения сравнения, числом, сравнимым с ним, т.е. с числом, принадлежащим к одному и тому же классу.
Другой элемент, который является общим для всех чисел данного класса, является наибольший общий делитель каждого элемента этого класса и модуля p .
Пусть a и b сравнимы по модулю p , тогда
Теорема 1. Если в ax+b вместо x подставим последовательно все p членов полной системы чисел
Поэтому все числа ax+b , где x =1,2,...p -1 не сравнимы по модулю p (в противном случае, числа 1,2,...p -1 были бы сравнимы по модулю p .
Примечания
1) В данной статье под словом число будем понимать целое число.
Литература
- 1. К.Айрленд, М.Роузен. Классическое введение в современную теорию чисел.− М:Мир, 1987.
- 2. Г.Дэвенпорт. Высшая арифметика.− М:Наука, 1965.
- 3. П.Г. Лежен Дирихле. Лекции по теории чисел. − Москва, 1936.
Как показано в §5, отношение сравнимости по модулю т обладает свойствами рефлексивности, симметричности и транзитивности; поэтому оно является отношением эквивалентности Возьмем произвольное целое число а. Обозначим через о множество чисел, сравнимых с а по модулю т: Пусть. Пусть теперь. И так далее. Процесс будет длиться до тех пор, пока построенные множества не будут покрывать все множество целых чисел. При этом возникает разбиение2> множества Z на множества а. Ь, с,..которые называют классами вычетов по модулю m; каждое число, входяшее в какой-нибудь из классов, называется вычетом этого класса. Число классов вычетов по модулю т равно т. Действительно, остаток отделения целого числа на т принимает одно из значений т - 2 или т - 1 и поэтому каждое из чисел попадает в один из классов 01, количество которых равно т. Взяв по одному числу из каждого класса вычетов получим систему представителей классов вычетов, или полную систему вычетов по модулю т. Системы вычетов Пример 1. Различные полные системы вычетов по модулю 7: Лемма 3. Числа, хт образуют полную систему вычетов по модулю т тогда и только тогда, когда они попарно не сравнимы по модулю т. Необходимость очевидна. Докажем достаточность. Если два числа не сравнимы по модулю ту то они попадают в разные классы вычетов. Так как всего классов вычетов m и рассматриваемых чисел гп, то они составляют полную систему вычетов. Лемма 4. Пусть,хт - полная система вычетов по модулю т, целое число а взаимно просто с т, b - произвольное целое число. Тогда числа ахi + 6, ах2 + Ь, ..ахт -f b также образуют полную систему вычетов. Согласно лемме 3 достаточно убедиться в том, чт Предположим (для приведения к противоречию), ч OG общем определении отношения и его свойствах речь пойдет ниже - в главе LXVIII; заметим, что теория чисел является источником многих важных примеров для обшей алгебры. Разбиение множества - это представление его в виде объединения попарно не пересекающихся подмножеств. Тогда a{xi-xj) \my и, поскольку (о, m) = 1, имеем (Xi-Xj) m, что противоречит лемме 3. Лемма 5. Пусть х = a(modm). Тогда (Системы вычетов м Действительно, пусть г - остаток от деления о на т. Тогда по лемме 2 Но так как х = a(mod т), при делении на m ««ело г"тамке имеет остаток г, и, следовательно, (я,т) = (г,т), откуда и вытекает требуемое. Итак, числа из одного класса вычетов по модулю т имеют один и тот же наибольший обший делитель с т. Поэтому становится корректным следующее определени е. Вычет по модулю т называют приведенным, если он взаимно прост с т. Совокупность приведенных вычетов из разных классов вычетов называют приведенной системой вычетов. Пример 2. При m = 7 приведенная система вычетов может выглядеть так: Системы вычетов Функцией Эйлера (р(т) называют число натуральных чисел, не превосходящих т и взаимно простьк с т. Например, . Легко видеть, что если р - простое число, Очевидно, что приведенная система вычетов по модулю т содержит чисел. Лемма 6. Пусть а взаимно просто приведенная система вычетов по модулю т. Тогда числа ах\, ах к также образуют приведенную систему вычетов по модулю т. 4 Так как числа о и Х{ взаимно просты с т, таким же свойством обладает и их произведение ах*. В силу леммы 4 числа ах\,ах2,... принадлежат к разным классам вычетов, и, следовательно, в силу предыдущего, образуют приведенную систему вычетов.