Согласно свойству сравнений №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. Пришли к противоречию, следовательно предположение о существовании обратного элемента неверно.
Итак, мы только что доказали
Теорему обратимости
a -1 (mod m ) (a , m ) = 1.
Суммируя все рассуждения этого пункта, можем сказать, что обратимыми являются только взаимно простые с модулем числа, и найти обратные для них можно с помощью расширенного алгоритма Евклида.
Согласно свойству сравнений №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 = 6. Тогда имеем шесть классов разбиения множества целых чисел по модулю 6:
r
= 1;
r
= 2;
r
= 3;
r
= 4;
r
= 5;
где через r обозначен остаток от деления целого числа на 6.
Напомним теорему о делении с остатком:
Теорема
: Разделить число на число , , с остатком, значит, найти пару целых чисел q
и r
, таких, что выполняются следующие условия: 
.
Легко доказывается, что для любых целых чисел а и деление с остатком возможно и числа q и r определяются однозначно. В нашем примере полная система наименьших неотрицательных вычетов есть множество {0, 1, 2, 3, 4, 5}; полная система наименьших положительных вычетов – множество {0, 1, 2, 3, 4, 5}; полная система наименьших по абсолютной величине вычетов – множество {-2,-1, 0, 1, 2, 3}; приведённая система вычетов – множество {1,5}, так как ; фактор-множество
Один из методов выполнения арифметических операций над данными целыми числами основан на простых положениях теории чисел. Идея этого метода состоит в том, что целые числа представляются в одной из непозиционных систем – в системе остаточных классов. А именно: вместо операций над целыми числами оперируют с остатками от деления этих чисел на заранее выбранные простые числа – модули 
.
Чаще всего числа выбирают из множества простых чисел.
Пусть 
…, 
.
Так как в кольце целых чисел имеет место теорема о делении с остатком, т. е. где , то кольцо Z , по определению, является евклидовым.
Таким образом, в качестве чисел можно выбрать остатки от деления числа А на р i соответственно.
Система вычетов позволяет осуществлять арифметические операции над конечным набором чисел, не выходя за его пределы. Полная система вычетов по модулю n ― любой набор из n попарно несравнимых по модулю n целых чисел. Обычно в качестве полной системы вычетов по модулю n берутся наименьшие неотрицательные вычеты
Делении целых чисел a и m получается частное q и остаток r , такие что
a = m q + r, 0 r m-1. Остаток r называют ВЫЧЕТ ом по модулю m .
Например, для m = 3 и для m =5 получим:
| a = m q + r, m = 3 | a = m q + r, m = 5 |
| 0 = 3 + 0 | 0 = 5 + 0 |
| 1 = 3 + 1 | 1 = 5 + 1 |
| 2 = 3 + 2 | 2 = 5 + 2 |
| 3 = 3 + 0 | 3 = 5 + 3 |
| 4 = 3 + 1 | 4 = 5 + 4 |
| 5 = 3 + 2 | 5 = 5 + 0 |
| 6 = 3 + 0 | 6 = 5 + 1 |
| 7 = 3 + 1 | 7 = 5 + 2 |
Если остаток равен нулю (r =0 ), то говорят, что m делит a нацело (или m кратно a ), что обозначают m a , а числа q и m называют делителями a . Очевидно 1 a и a a . Если a не имеет других делителей, кроме 1 и а , то а – простое число, иначе а называют составным числом. Самый большой положительный делитель d двух чисел a и m называют наибольшим общим делителем (НОД) и обозначают d = (a,m). Если НОД (a,m)= 1 , то a и m не имеют общих делителей, кроме 1 , и называются взаимно простыми относительно друг друга.
Каждому ВЫЧЕТ у r = 0, 1, 2,…, m-1 соответствует множество целых чисел a, b, … Говорят, что числа с одинаковым ВЫЧЕТ ом сравнимы по модулю и обозначают a b(mod m) или (a b) m .
Например, при m = 3 :
Например, при m = 5 :
Числа а , которые сравнимы по модулю m , образуют класс своего ВЫЧЕТа r и определяются как a = m q + r.
Числа а тоже называют ВЫЧЕТами по модулю m . НеотрицательныеВЫЧЕТы а = r (при q=0 ), принимающие значения из интервала , образуют полную систему наименьших вычетов по модулю m.
ВЫЧЕТы а
, принимающие значения из интервала [-( ,…,( ]
, при нечетном m
или из интервала [-
при четном m
образуют полную систему абсолютно наименьших ВЫЧЕТ
ов по модулю m.
Например, при m = 5 классы наименьших вычетов образуют
r = 0, 1, 2, 3, 4, a = -2, -1, 0, 1, 2. Обе приведенные совокупности чисел образуют полные системы вычет ов по модулю 5 .
Класс ВЫЧЕТов , элементы которого взаимно просты с модулем m
называют приведенным. Функция Эйлера определяет сколько ВЫЧЕТов из полной системы наименьших вычетов по модулю m взаимно просты с m . При простом m=p имеем = p-1.
Определение . Максимальный набор попарно несравнимых по модулю m чисел, взаимно простых с m , называется приведённой системой вычетов по модулю m . Всякая приведённая система вычетов по модулю m содержит элементов, где - функция Эйлера.
Определение. Любое число из класса эквивалентности є m будем называть вычет ом по модулю m . Совокупность вычет ов, взятых по одному из каждого класса эквивалентности є m , называется полной системой вычет ов по модулю m (в полной системе вычет ов, таким образом, всего m штук чисел). Непосредственно сами остатки при делении на m называются наименьшими неотрицательными вычет ами и, конечно, образуют полную систему вычет ов по модулю m . Вычет r называется абсолютно наименьшим, если ïrï наименьший среди модулей вычет ов данного класса.
Пример . Проверить, образуют ли числа 13, 8, - 3, 10, 35, 60 полную систему вычетов по модулю m=6.
Решение : По определению числа образуют полную систему вычетов по модулю m , если их ровно m и они попарно несравнимы по модулюm .
Попарную несравнимость можно проверить, заменив каждое число наименьшим неотрицательным вычетом; если повторений не будет, то это полная система вычетов.
Применим теорему о делении с остатком: a = m q + r.
13 = 6 2 + 1 13 1(mod 6); 8 = 6 1 + 2 8 2(mod 6);
3 = 6 (-1) + 3 -3 3(mod 6); 10 = 6 1 + 4 10 4(mod 6);
35 = 6 5 + 5 35 5(mod 6); 60 = 6 10 + 0 60 0(mod 6).
Получили последовательность чисел: 1, 2, 3, 4, 5, 0, их ровно 6, повторений нет и они попарно несравнимы. То есть, они образуют полную систему вычетов по модулю m = 6.
Пример . Заменить наименьшим по абсолютной величине, а также наименьшим положительным вычетом 185 по модулю 16.
Решение. Применим теорему о делении с остатком:
185 = 16 11 + 9 185 9(mod 16).
Пример. Проверить, образуют ли числа (13, -13, 29, -9) приведенную систему вычетов по модулю m=10.
Решение: Всякая приведённая система вычетов по модулю m содержит элементов, где - функция Эйлера. В нашем случае =4, ибо среди натуральных чисел только 1, 3, 7, 9 взаимно просты с 10 и не превосходят его. То есть, возможно, что эти четыре числа составляют искомую систему. Проверим эти числа на их попарную несравнимость: =4, ибо среди натуральных чисел только 1, 3, 7, 9 взаимно просты с 10 и не превосходят его. То есть, возможно, что эти четыре числа составляют искомую систему. Проверим эти числа на их попарную несравнимость:m .
Вариант 1. a = 185, m = 12; Вариант 2. a = 84, m = 9;
Вариант 3. a = 180, m = 10; Вариант 4. a = 82, m = 9;
Вариант 5. a = 85, m = 11; Вариант 6. a = 84, m = 8;
Вариант 7. a = 103, m = 87; Вариант 8. a = 84, m = 16;
Вариант 9. a = 15, m = 10; Вариант 10. a = 81, m = 9;
Вариант 11. a = 85, m = 15; Вариант 12. a = 74, m = 13;
Вариант 13. a = 185, m = 16; Вариант 14. a = 14, m = 9;
Вариант 15. a = 100, m = 11; Вариант 16. a = 484, m = 15;
Вариант 17. a = 153, m = 61; Вариант 18. a = 217, m = 19;
Вариант 19. a = 625, m = 25; Вариант 20. a = 624, m = 25;
Задание 3. Записать полную и приведенную систему наименьших
В частности, будем иметь (p a) = p a - p a-1 , (p) = p-1.
Примеры. (60) = 60
(81) = 81-27 = 54
Мультипликативная функция
Функция (а) называется мультипликативной, если она удовлетворяет двум следующим условиям:
Эта функция определена для всех целых положительных a и не равна нулю по меньшей мере при одном таком a.
Для любых положительных взаимно простых a 1 и a 2 имеем:
(а 1 a 2) = (а 1) (а 2) .
Основные понятия теории сравнений
Свойства сравнений
Мы будем рассматривать целые числа в связи с остатками от деления их на данное целое положительное m, которое назовём модулем.
Каждому целому числу отвечает определённый остаток от деления его на m. Если двум целым a и b отвечает один и тот же остаток r, то они называются равноостаточными по модулю m.
Сравнимость чисел a и b по модулю m записывается:
Сравнимость чисел a и b по модулю m равносильна:
Возможности представить a в виде a = b + mt, где t - целое.
Делимости a b на m.
Действительно, из a b (mod m) следует
a = mq + r, b = mq 1 + r, 0<= r откуда a - b = m (q - q 1), a = b + mt, t = q - q 1 . Обратно, из a = b + mt, представляя b в виде b = mq 1 + r , 0 <=r выводим a = mq + r, q = q 1 + t , т.е. a b (mod m). Оба утверждения доказаны. Два числа, сравнимые с третьим, сравнимы между собой. Сравнения можно почленно складывать. Действительно, пусть A 1 b 1 (mod m) , a 2 b 2 (mod m) , …, a k b k (mod m) (1). Тогда a 1 = b 1 + mt 1 , a 2 = b 2 + mt 2 , …, a k = b k + mt k (2), Откуда a 1 + a 2 + … + a k = b 1 + b 2 + … + b k + m (t 1 + t 2 + … + t k), или a 1 + a 2 + … + a k b 1 + b 2 + … + b k (mod m). Сравнения можно почленно перемножать. Рассмотрим (1) и (2). Перемножая почленно равенства (2), получим: a 1 a 2 …a k b 1 b 2 …b k + mN, где N - целое. Отсюда: a 1 a 2 …a k b 1 b 2 …b k (mod m). Обе части сравнения можно возвести в одну и ту же степень. Обе части сравнения можно умножить на одно и то же целое число. Действительно, перемножив сравнение a b (mod m) с очевидным сравнением k k (mod m), получим ak bk (mod m). Обе части сравнения можно разделить на их общий делитель, если последний взаимно прост с модулем. Действительно, из a b (mod m), a = a 1 d , b = b 1 d , (d, m) = 1 следует, что разность a - b, равная (a 1 - b 1)d, делится на m, т. е. a 1 b 1 (mod m) . Числа равноостаточные, или, что то же самое, сравнимые по модулю m, образуют класс чисел по модулю m. Из такого определения следует, что всем числам класса отвечает один и тот же остаток r, и мы получим все числа класса, если в форме mq + r заставим q пробегать все целые числа. Соответственно m различным значениям r имеем m классов чисел по модулю m. Любое число класса называется вычетом по модулю m по отношению ко всем числам того же класса. Вычет, получаемый при q = 0, равный самому остатку r, называется наименьшим неотрицательным вычетом. Взяв от каждого класса по одному вычету, получим полную систему вычетов по модулю m. Чаще всего в качестве полной системы вычетов употребляют наименьшие неотрицательные вычеты 0, 1, ..., m-1 или также абсолютно наименьшие вычеты. Последние, как это следует из вышеизложенного, в случае нечетного m представляются рядом 1, 0, 1, ..., а в случае чётного m каким-либо из двух рядов 1, 0, 1, ..., 1, 0, 1, ..., . Любые m чисел, попарно несравнимые по модулю m, образуют полную систему вычетов по этому модулю. Действительно, будучи несравнимы, эти числа тем самым принадлежат к различным классам, а так как их m, т.е. столько же, сколько и классов, то в каждый класс наверно попадёт по одному числу. Если (a, m) = 1 и x пробегает полную систему вычетов по модулю m, то ax + b, где b - любое целое, тоже пробегает полную систему вычетов по модулю m. Действительно, чисел ax +b будет столько же, сколько и чисел x, т.е. m. Согласно предыдущему утверждению остаётся, следовательно, только показать, что любые два числа ax 1 + b и ax 2 + b, отвечающие несравнимым x 1 и x 2 , будут сами несравнимы по модулю m. Но допустив, что ax 1 + b ax 2 + b (mod m), мы придём к сравнению ax 1 = ax 2 (mod m), откуда, вследствие (a, m) = 1, получим x 1 x 2 (mod m), что противоречит предположению о несравнимости чисел x 1 и x 2 . Числа одного и того же класса по модулю m имеют с модулем один и тот же общий наибольший делитель. Особенно важны классы, для которых этот делитель равен единице, т.е. классы, содержащие числа, взаимно простые с модулем. Взяв от каждого такого класса по одному вычету, получим приведённую систему вычетов по модулю m. Приведённую систему вычетов, следовательно, можно составить из чисел полной системы, взаимно простых с модулем. Обыкновенно приведённую систему вычетов выделяют из системы наименьших неотрицательных вычетов: 0, 1, ..., m-1. Так как среди этих чисел число взаимно простых с m есть (m), то число чисел приведённой системы, равно как и число классов, содержащих числа, взаимно простые с модулем, есть (m). Пример. Приведённая система вычетов по модулю 42 будет 1, 5, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41. Любые (m) чисел, попарно несравнимые по модулю m и взаимно простые с модулем, образуют приведённую систему вычетов по модулю m. Действительно, будучи несравнимыми и взаимно простыми с модулем, эти числа тем самым принадлежат к различным классам, содержащим числа, взаимно простые с модулем, а так как их (m), т.е. столько же, сколько и классов указанного вида, то в каждый класс наверно попадёт по одному числу. Если (a, m) = 1 и x пробегает приведённую систему вычетов по модулю m, то ax тоже пробегает приведённую систему вычетов по модулю m. Действительно, чисел ax будет столько же, сколько и чисел x, т.е. (m). Согласно предыдущему свойству остаётся, следовательно, только показать, что числа ax по модулю m несравнимы и взаимно просты с модулем. Первое следует из свойства сравнений (если сравнение имеет место по модулю m, то оно имеет место и по модулю d, равному любому делителю числа m) для чисел более общего вида ax + b, второе же следует из (a, m) = 1, (x, m) = 1. Теорема Эйлера (2. 5. 3. 1). При m>1 и (a, m) = 1 имеем a (m) 1 (mod m). Доказательство. Действительно, если x пробегает приведённую систему вычетов x = r 1 , r 2 , ..., r c ; c = (m), составленную из наименьших неотрицательных вычетов, то наименьшие неотрицательные вычеты 1 , 2 , ..., с чисел ax будут пробегать ту же систему, но расположенную, вообще говоря, в ином порядке (1). Перемножая почленно сравнения ar 1 1 (mod m), ar 2 2 (mod m), ..., ar c c (mod m), получим а с 1 (mod m). Теорема Ферма (2. 5. 3. 2). При p простом и а, не делящимся на p, имеем a p-1 1 (mod p). (2) Доказательство. Эта теорема является следствием теоремы Эйлера при m = p. Теореме Ферма можно придать более удобную форму, умножая обе части сравнения (2) на а, получим сравнение a p a (mod p), справедливое уже при всех целых а, так как оно верно и при а, кратном p. Теорема доказана. Теорема (2. 5. 3. 3). Если n = pq, (p и q - отличные друг от друга простые числа), то (n) = (p-1)(q-1). Теорема (2. 5. 3. 4). Если n = pq, (p и q отличные друг от друга простые числа) и x простое относительно p и q, то x (n) = 1 (mod n). или же любые последовательные 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) В данной статье под словом число будем понимать целое число.Вычеты. Полная и приведенная системы вычетов
Теоремы Эйлера и Ферма
Примечания
Литература
