Полная система вычетов модулю m. Полная и приведенная системы вычетов. Теоремы Эйлера и Ферма. Краткие сведения из теории

Обычно в качестве полной системы вычетов по модулю m берутся наименьшие неотрицательные вычеты

0,1,...,m − 1

или абсолютно наименьшие вычеты, состоящие из чисел

в случае нечётного m и чисел

в случае чётного m .

См. также

Литература

И. М. Виноградов Основы теории чисел . - М.-Л.: Гос. изд. технико-теоретической литературы, 1952. - 180 с.

Wikimedia Foundation . 2010 .

Смотреть что такое "Полная система вычетов" в других словарях:

По модулю m, любая совокупность целых чисел, содержащая по одному числу из каждого класса чисел по модулю m (два целых числа а и b принадлежат одному классу по модулю m, если а b делится на m; см. Вычет). В качестве П. с. в. чаще всего… …

По модулю т любой набор из тнесравнимых между собой по модулю тцелых чисел. Обычно в качестве П. с. в. по модулю тберутся наименьшие неотрицательные вычеты 0, 1, . . ., т 1 или абсолютно наименьшие вычеты, состоящие из чисел 0, +1, . . ., в… … Математическая энциклопедия

Часть полной системы вычетов (См. Полная система вычетов), состоящая из чисел взаимно простых с модулем m. П. с. в. содержит φ(m) чисел [φ(m) число чисел, взаимно простых с m и меньших m]. Всякие φ(m) чисел, не сравнимые по модулю m и… … Большая советская энциклопедия

Сравнение по модулю натурального числа n в теории чисел отношение эквивалентности на кольце целых чисел, связанное с делимостью на n. Факторкольцо по этому отношению называется кольцом вычетов. Совокупность соответствующих тождеств и… … Википедия

В теории чисел сравнение[уточнить] по модулю натурального числа n задаваемое означенным числом отношение эквивалентности на множестве целых чисел, связанное с делимостью на него. Факторпространство по этому отношению называется «кольцом… … Википедия

Симметрия снежинки связана с группой поворотов на угол, кратный 60° Конечная группа алгебраическая группа, содержащая конечное число элементов (это число называется её порядком). Далее группа предполагается мультипликативной, то есть операция в… … Википедия

Функция, к рая может быть представлена степенным рядом. Исключит, важность класса А. ф. определяется следующим. Во первых, этот класс достаточно ш и р о к: он охватывает большинство функций, встречающихся в основных вопросах математики и ее… … Математическая энциклопедия

I Содержание: I. Начальное народное образование вообще. II. Начальное народное образование за границей: Австро Венгрия, Англия, Бельгия, Болгария, Германия, Голландия, Дания, Испания, Италия, Норвегия, Португалия, Румыния, Сербия,… … Энциклопедический словарь Ф.А. Брокгауза и И.А. Ефрона

- — родился 26 мая 1799 г. в Москве, на Немецкой улице в доме Скворцова; умер 29 января 1837 г. в Петербурге. Со стороны отца Пушкин принадлежал к старинному дворянскому роду, происходившему, по сказанию родословных, от выходца "из… … Большая биографическая энциклопедия

Совокупность замкнутых формул логики предикатов 1 й ступени. Э. т. Th(К) класса К алгебраических систем сигнатуры наз. совокупность всех замкнутых формул логики предикатов 1 й ступени сигнатуры истинных на всех системах из класса К. Если класс… … Математическая энциклопедия

или же любые последовательные 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.

Согласно свойству сравнений №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 . Совокупность вычетов, взятых по одному из каждого класса эквивалентности  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 ) – функция Мебиуса.