Полная система вычетов модулю m. Системы вычетов

Пункт 17. Полная и приведенная системы вычетов.

В предыдущем пункте было отмечено, что отношение є m сравнимости по произвольному модулю m есть отношение эквивалентности на множестве целых чисел. Это отношение эквивалентности индуцирует разбиение множества целых чисел на классы эквивалентных между собой элементов, т.е. в один класс объединяются числа, дающие при делении на m одинаковые остатки. Число классов эквивалентности є m (знатоки скажут - "индекс эквивалентности є m ") в точности равно m .

Определение. Любое число из класса эквивалентности є m будем называть вычетом по модулю m . Совокупность вычетов, взятых по одному из каждого класса эквивалентности є m , называется полной системой вычетов по модулю m (в полной системе вычетов, таким образом, всего m штук чисел). Непосредственно сами остатки при делении на m называются наименьшими неотрицательными вычетами и, конечно, образуют полную систему вычетов по модулю m . Вычет r называется абсолютно наименьшим, если пrп наименьший среди модулей вычетов данного класса.

Пример : Пусть 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 содержит j ( m ) штук вычетов, где j ( m )– функция Эйлера – число чисел, меньших m и взаимно простых с m . Если к этому моменту вы уже забыли функцию Эйлера, загляните в пункт 14 и убедитесь, что про нее там кое-что говорилось.

Пример. Пусть m = 42. Тогда приведенная система вычетов суть:

1, 5, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41.

Лемма 2. 1) Любые j ( m ) чисел, попарно не сравнимые по модулю m и взаимно простые с модулем, образуют приведенную систему вычетов по модулю m .

2) Если (a,m) = 1 и x пробегает приведенную систему вычетов по модулю m , то аx так же пробегает приведенную систему вычетов по модулю m .

Доказательство. Утверждение 1) – очевидно. Докажем утверждение 2). Числа аx попарно несравнимы (это доказывается так же, как в лемме 1 этого пункта), их ровно j ( m ) штук. Ясно также, что все они взаимно просты с модулем, ибо (a,m)=1, (x,m)=1 Ю (ax.m)=1 . Значит, числа аx образуют приведенную систему вычетов.

Таковы определения и основные свойства полной и приведенной систем вычетов, однако в багаже математических знаний существует еще целый ряд очень интересных и полезных фактов, касающихся систем вычетов. Если умолчать про них в этом пункте, то это, боюсь, будет прямым нарушением Закона Российской Федерации об Информации, злонамеренное утаивание которой является, согласно этому закону, административно и, даже, уголовно наказуемым деянием. Кроме того, без знакомства с дальнейшими важными свойствами систем вычетов пункт 17 получится весьма куцым. Продолжим.

Лемма 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 , где

1) Если x 1 , x 2 , ..., x k пробегают полные системы вычетов по модулям m 1 , m 2 , ..., m k пробегают полную систему вычетов по модулю m=m 1 m 2 ...m k .

2) Если x 1 , x 2 , ..., x k пробегают приведенные системы вычетов по модулям m 1 , m 2 , ..., m k соответственно, то значения линейной формы пробегают приведенную систему вычетов по модулю m=m 1 m 2 ...m k .

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

1) Форма M 1 x 1 +M 2 x 2 + ...+M k x k принимает, очевидно, m 1 m 2 ...m k =m значений. Покажем, что эти значения попарно несравнимы. Ну пусть

M 1 x 1 +M 2 x 2 + ...+M k x k є M 1 x 1 С +M 2 x 2 С + ...+M k x k С (mod m)

Всякое M j , отличное от M s , кратно m s . Убирая слева и справа в последнем сравнении слагаемые, кратные m s , получим:

M s x s є M s x s С (mod m s) Ю x s є x s С (mod m s)

– противоречие с тем, что x s пробегает полную систему вычетов по модулю m s .

2). Форма M 1 x 1 +M 2 x 2 + ...+M k x k принимает, очевидно, j ( m 1 ) j ( m 2 ) Ч ... Ч j ( m k ) = j ( m 1 m 2 Ч ... Ч m k )= j ( m ) (функция Эйлера мультипликативна!) различных значений, которые между собой по модулю m=m 1 m 2 ...m k попарно несравнимы. Последнее легко доказывается рассуждениями, аналогичными рассуждениям, проведенным при доказательстве утверждения 1) этой леммы. Так как ( M 1 x 1 +M 2 x 2 + ...+M k x k ,m s)=(M s x s ,m s)=1 для каждого 1 Ј s Ј k , то ( M 1 x 1 +M 2 x 2 + ...+M k x k ,m s)=1 , следовательно множество значений формы M 1 x 1 +M 2 x 2 + ...+M k x k образует приведенную систему вычетов по модулю m .

Лемма 4. Пусть x 1 , x 2 , ..., x k ,x пробегают полные, а x 1 , x 2 ,..., x k , x – пробегают приведенные системы вычетов по модулям m 1 , m 2 , ..., m k и m=m 1 m 2 ...m k соответственно, где (m i m j)=1 при i № j . Тогда дроби совпадают с дробями {x/m} , а дроби совпадают с дробями { x /m} .

Доказательство. Доказательство обоих утверждений леммы 4 легко получается применением предыдущей леммы 3 после того, как вы приведете каждую сумму {x 1 /m 1 +x 2 /m 2 +...+x k /m k } и { x 1 /m 1 + x 2 /m 2 +...+ x k /m k } к общему знаменателю:

{x 1 /m 1 +x 2 /m 2 +...+x k /m k }={(M 1 x 1 +M 2 x 2 +...+M k x k)/m} ;

{ x 1 /m 1 + x 2 /m 2 +...+ x k /m k }={(M 1 x 1 +M 2 x 2 +...+M k x k)/m} ,

где M j =m 1 ...m j-1 m j+1 ...m k .

Если теперь принять во внимание, что дробные части чисел, получающихся при делении на модуль m любых двух чисел, сравнимых по модулю m , одинаковы (они равны r/m , где r – наименьший неотрицательный вычет из данного класса), то утверждения настоящей леммы становятся очевидными.

В оставшейся части этого пункта произойдет самое интересное – мы будем суммировать комплексные корни m -ой степени из единицы, при этом нам откроются поразительные связи между суммами корней, системами вычетов и уже знакомой мультипликативной функцией Мебиуса m ( m ) .

Обозначим через e k k -ый корень m- ой степени из единицы:

Эти формы записи комплексных чисел мы хорошо помним с первого курса. Здесь k=0,1,...,m-1 – пробегает полную систему вычетов по модулю m .

Напомню, что сумма e 0 + e 1 +...+ e m-1 всех корней m -ой степени из единицы равна нулю для любого m . Действительно, пусть e 0 + e 1 +...+ e m-1 =a . Умножим эту сумму на ненулевое число e 1 . Такое умножение геометрически в комплексной плоскости означает поворот правильного m -угольника, в вершинах которого расположены корни e 0 , e 1 ,..., e m-1 , на ненулевой угол 2 p /m . Ясно, что при этом корень e 0 перейдет в корень e 1 , корень e 1 перейдет в корень e 2 , и т.д., а корень e m-1 перейдет в корень e 0 , т.е. сумма e 0 + e 1 +...+ e m-1 не изменится. Имеем e 1 a=a , откуда a=0 .

Теорема 1. Пусть m>0 - целое число, a О Z , x пробегает полную систему вычетов по модулю m . Тогда, если а кратно m , то

в противном случае, при а не кратном m ,

.

Доказательство. При а кратном m имеем: a=md и

При а не делящемся на m , разделим числитель и знаменатель дроби a/m на d – наибольший общий делитель а и m , получим несократимую дробь a 1 /m 1 . Тогда, по лемме 1, a 1 x будет пробегать полную систему вычетов по модулю m . Имеем:

ибо сумма всех корней степени m 1 из единицы равна нулю.

Напомню, что корень e k m -ой степени из единицы называется первообразным, если его индекс k взаимно прост с m . В этом случае, как доказывалось на первом курсе, последовательные степени e k 1 , e k 2 ,..., e k m-1 корня e k образуют всю совокупность корней m -ой степени из единицы или, другими словами, e k является порождающим элементом циклической группы всех корней m -ой степени из единицы.

Очевидно, что число различных первообразных корней m -ой степени из единицы равно j ( m ), где j – функция Эйлера, так как индексы у первообразных корней образуют приведенную систему вычетов по модулю m .

Теорема 2. Пусть m>0 – целое число, x пробегает приведенную систему вычетов по модулю m . Тогда (сумма первообразных корней степени m ):

где m ( m ) – функция Мебиуса.

Доказательство. Пусть m=p 1 a 1 p 2 a 2 ...p k a k – каноническое разложение числа m ; m 1 =p 1 a 1 , m 2 =p 2 a 2 , m 3 =p 3 a 3 ; x i пробегает приведенную систему вычетов по модулю m i . Имеем:

При a s =1 получается, что только корень e 0 =1 не является первообразным, поэтому сумма всех первообразных корней есть сумма всех корней минус единица:

стало быть, если m свободно от квадратов (т.е. не делится на r 2 , при r >1 ), то

Если же какой-нибудь показатель a s больше единицы (т.е. m делится на r 2 , при r>1 ), то сумма всех первообразных корней степени m s есть сумма всех корней степени m s минус сумма всех не первообразных корней, т.е. всех корней некоторой степени, меньшей m s . Именно, если m s =p s m s * , то:

Вот теперь, дорогие читатели, когда я представил на ваше рассмотрение довольно весьма значительное количество сведений про полные и приведенные системы вычетов, никто не сможет обвинить меня в злонамеренном нарушении Закона Российской Федерации об Информации посредством ее утаивания, поэтому я заканчиваю этот пункт с удовлетворением.

Классы вычетов. Системы вычетов

Краткие сведения из теории

Применяя теорему о делении с остатком можно множество целых чисел разбить на ряд классов. Рассмотрим пример. Пусть 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 получим:

Если остаток равен нулю (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. Записать полную и приведенную систему наименьших

ОСНОВНЫЕ СВЕДЕНИЯ ИЗ ТЕОРИИ

6. 1. Определение 1.

Классом чисел по данному модулю т называется множество всех тех и только тех целых чисел, которые при делении на т имеют один и тот же остаток r, то есть сравнимых по модулю т (т ÎN, т > 1).

Обозначение класса чисел, имеющих остаток r : .

Каждое число из класса называется вычетом по модулю т, а сам класс называется классом вычетов по модулю т.

6. 2. Свойства множества классов вычетов по модулю т :

1) всего по модулю т будет т классоввычетов: Z т = { , , , … , };

2) каждый класс содержит бесконечное множество целых чисел (вычетов) вида: = {a = mq + r / q ÎZ, 0£ r < m }

3) "а Î : а º r (mod m );

4) "а, b Î : а º b (mod m ), то есть любые два вычета, взятые из одного класса, сравнимы по модулю т ;

5) "а Î , "b Î : а b (mod m ), то есть никакие два вычета; взятые из разных классов, несравнимы по модулю т .

6. 3. Определение 3.

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

Пример: если m = 5, то {10, 6, – 3, 28, 44} – это полная система вычетов по модулю 5 (причём, не единственная!)

В частности,

множество {0, 1, 2, 3, … , m –1} – это система наименьших неотрицательных вычетов;

множество {1, 2, 3, … , m –1, т }– это система наименьших положительных вычетов.

6. 4. Отметим, что:

если {х 1 , х 2 , … , х т } – полная система вычетов по модулю т , то

.

6. 5. Теорема 1.

Если {х 1 , х 2 , … , х т } – полная система вычетов по модулю т , "а, b Î Z и (а, т ) = 1, – то система чисел {ах 1 + b , ах 2 + b , … , ах т + b }также образует полную систему вычетов по модулю т .

6. 6. Теорема 2.

Все вычеты одного и того же класса вычетов по модулю т имеют с числом т один и тот же наибольший общий делитель: "а, b Î Þ (а; т ) = (b; т ).

6. 7. Определение 4.

Класс вычетов по данному модулю т называется взаимно простым с модулем т , если хотя бы один вычет этого класса – взаимно простой с т.

Заметим, что в этом случае по теореме 2 все числа этого класса будут взаимно простыми с модулем т.

6. 8. Определение 5.

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

6. 9. Отметим, что:

1) приведённая система вычетов по модулю т содержит j(т ) чисел {х 1 , х 2 ,…, };

2) : .

3) " х i : (х i , m ) = 1;

Пример : Пусть по модулю т = 10 имеется 10классоввычетов:

Z 10 = { , , , , , , , , , }– множество классоввычетов по модулю 10. Полная система вычетов по mod 10 будет, например, такая: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.

Множество классов вычетов, взаимно простых с модулем m= 10: { , , , }(j(10) = 4).

Приведённая система вычетов по модулю10 будет, например,

{1, 3, 7, 9}, или {11, 43, – 5, 17}, или { – 9, 13, – 5, 77} и т.д. (везде j(10) = 4 числа).

6.10. Практически: чтобы составить одну из возможных приведённых систем вычетов по mod m , нужно из полной системы вычетов по mod m выбрать те вычеты, которые взаимно простые с т. Таких чисел будет j(т ).

6.11. Теорема 3.

Если {х 1 , х 2 ,…, } – приведённая система вычетов по модулю т и

(а , m ) = 1, – то система чисел {ах 1 , ах 2 , … , ах j (т) } также образует

приведённую систему вычетов по модулю т .

6.12. Определение 6.

Суммой ( Å ) классов вычетов и + b, равных сумме любых двух вычетов, взятых по одному из каждого данного класса и : Å = , где "а Î , "b Î .

6.13. Определение 7.

Произведением ( Ä ) классов вычетов и по модулю т называется класс вычетов , то есть класс вычетов, состоящий из чисел а ´ b, равных произведению любых двух вычетов, взятых по одному из каждого данного класса и : Ä = , где "а Î , "b Î .

Таким образом, в множестве классов вычетов по модулю т : Z т = { , , ,…, } определены две алгебраические операции – "сложения" и "умножения".

6.14. Теорема 4.

Множество классов вычетов Z т по модулю т является ассоциативно-коммутативным кольцом с единицей:

< Z т , +, · > = < { , , ,…, }, +, · > – кольцо.

ТИПОВЫЕ ЗАДАЧИ

1. Составить по модулю т = 9:

1) полную систему наименьших положительных вычетов;

2) полную систему наименьших неотрицательных вычетов;

3) произвольную полную систему вычетов;

4) полную систему наименьших по абсолютной величине вычетов.

Ответ :1) {1, 2, 3, 4, 5, 6, 7, 8, 9}; 2) {0, 1, 2, 3, 4, 5, 6, 7, 8};

2. Составить приведённую систему вычетов по модулю т = 12.

Решение.

1) Составим полную систему наименьших положительных вычетов по модулю т = 12:

{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12} (всего т = 12 чисел).

2) Вычеркнем из этой системы числа, не взаимно простые с числом 12:

{1, 2 , 3 , 4 , 5, 6 , 7, 8 , 9 , 10 , 11, 12 }.

3) Оставшиеся числа, взаимно простые с числом 12, образуют искомую приведённую систему вычетов по модулю т = 12 (всего j(т ) = j(12) = 4 числа).

Ответ: {1, 5, 7, 11} – приведённая система вычетов по модулю т = 12.

130. Составьте 1) полную систему наименьших положительных вычетов; 2) полную систему наименьших неотрицательных вычетов; 3) произвольную систему вычетов; 4) полную систему наименьших по абсолютной величине вычетов; 5) приведённую систему вычетов: а) по модулю m = 6; б) по модулю m = 8.

131. Является ли множество {9, 2, 16, 20, 27, 39, 46, 85} полной системой вычетов по модулю 8 ?

132 По какому модулю множество{20, – 4, 22, 18, – 1}является полной системой вычетов?

133. Составьте приведённую систему вычетов по модулю m , если а) m = 9; б) m = 24; в) m = 7. Сколько чисел должна содержать такая система?

134. Сформулируйте основные свойства полной системы вычетов и приведённой системы вычетов по модулю m .

135. Какими элементами отличаются приведённая и полная системы наименьших неотрицательных вычетов по простому модулю?

136. При каком условии числа а и – а принадлежат одному классу вычетов по модулю m ?

137. Каким классам вычетов по модулю 8 принадлежат все простые числа р ³ 3 ?

138. Образует ли множество чисел {0, 2 0 , 2 1 , 2 2 , ... , 2 9 } полную систему вычетов по модулю 11 ?

139. Скольким классам вычетов по модулю 21 принадлежат все вычеты из одного класса вычетов по модулю 7 ?

140. Множество целых чисел Z распределите по классам вычетов по модулю 5. Составьте таблицы сложения и умножения в образовавшемся множестве классов вычетов Z 5 . Является ли множество Z 5: а) группой с операцией сложения классов? б) группой с операцией умножения классов?

§ 7. ТЕОРЕМА ЭЙЛЕРА. МАЛАЯ ТЕОРЕМА ФЕРМА

ОСНОВНЫЕ СВЕДЕНИЯ ИЗ ТЕОРИИ

7. 1. Теорема 1.

Если а ÎZ , т ÎN, т >1 и (а ; т ) = 1 , – то в бесконечной последовательности степеней а 1 , а 2 , а 3 , ... , а s , … , а t , … найдутся хотя бы две степени с показателями s и t (s < t ) такие, что . (*)

7. 2. Замечание . Обозначив t – s = k > 0, из (*) получим: . Возводя обе части этого сравнения в степень n ÎN , получим: (**). Это означает, что существует бесконечное множество степеней числа a , удовлетворяющих сравнению (**). Но как найти эти показатели? Каков наименьший показатель, удовлетворяющий сравнению (**) ? На первый вопрос отвечает теорема Эйлера (1707 – 1783).

7. 3. Теорема Эйлера.

Если а ÎZ , т ÎN, т >1 и (а ; т ) = 1, – то . (13)

Пример. Пусть а = 2, т = 21, (а ; т ) = (2; 21) = 1. Тогда . Так как j (21) = 12, то 2 12 º 1(mod 21). В самом деле: 2 12 = 4096 и (4096 – 1) 21. Тогда очевидно, что 2 24 º 1(mod 21), 2 36 º 1(mod 21) и так далее. Но является ли показатель степени 12 – наименьшим , удовлетворяющим сравнению 2 n º 1(mod 21) ? Оказывается, нет. Наименьшим показателем будет п = 6: 2 6 º 1(mod 21), ибо 2 6 – 1 = 63, а 63 21. Заметим, что наименьший показатель следует искать только среди делителей числа j(т ) (в данном примере – среди делителей числа j(21) = 12).

7. 4. Малая теорема Ферма (1601 – 1665).

Для любого простого числа р и любого числа а ÎZ , не делящегося на р , имеет место сравнение . (14)

Пример. Пусть а = 3, р = 5, где 3 не 5. Тогда или .

7. 5. Обобщёння теорема Ферма.

Для любого простого числа р и произвольного числа а ÎZ имеет место сравнение (15)

ТИПОВЫЕ ЗАДАЧИ

1. Докажите, что 38 73 º 3(mod 35).

Решение.

1) Так как (38; 35) = 1, то по теореме Эйлера ; j(35) = 24, значит,

(1).

2) Из сравнения (1) по следствию 2 свойства 5 0 числовых сравнений имеем:

3) Из сравнения (2) по следствию 1 свойства 5 0 сравнений: 38 72 ×38 º 1×38 (mod 35) Þ Þ38 73 º38 º 38–35 = 3(mod 35) Þ 38 73 º 3 (mod 35), что и требовалось доказать.

2. Дано: а = 4, т = 15. Найти наименьший показатель степени k , удовлетворяющий сравнению (*)

Решение.

1) Так как (a ; m ) = (4; 25) = 1, то по теореме Эйлера , j(25) = 20, поэтому .

2) Является ли найденный показатель степени – число 20 – наименьшим натуральным числом, удовлетворяющим сравнению (*)? Если существует показатель степени, меньший 20, то он должен быть делителем числа 20. Значит, искомый наименьший показатель k надо искать среди множества чисел n = {1, 2, 4, 5, 10, 20}– делителей числа 20.

3) При п = 1: ;

при п = 2: ;

при п = 3: (рассматривать не надо);

при п = 4: ;

при п = 5: ;

при п = 6, 7, 8, 9: (рассматривать не надо);

при п = 10: .

Итак, наименьшим показателем степени k , удовлетворяющим сравнению(*), является k = 10.

Ответ: .

УПРАЖНЕНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ

141. По теореме Эйлера . При а = 3, т = 6 имеем: .

Так как j(6) = 2, то 3 2 º1(mod 6), или 9º1(mod 6), Тогда, по лемме, (9 – 1) 6 или 8 6 (нацело!?). Где ошибка?

142. Докажите, что: а) 23 100 º1(mod 101); б) 81 40 º 1(mod100); в) 2 73 º 2 (mod 73).

143. Докажите, что а) 1 16 + 3 16 + 7 16 + 9 16 º 4 (mod 10);

б) 5 4п + 1 + 7 4п + 1 делится без остатка на 12..

144. Докажите теорему, обратную теореме Эйлера: если а j ( m ) º 1(mod m ), то (а, m ) =1.

145. Найдите наименьший показатель степени k ÎN, удовлетворяющий данному сравнению: а) ; б) ; в) ; г) ;

д) ; е) ; ж) ; з) .

и) ; к) ; л) ; м) .

146. Найдите остаток от деления:

а) 7 100 на 11; б) 9 900 на 5; в) 5 176 на 7; г) 2 1999 на 5; д) 8 377 на 5;

е) 26 57 на 35; ж) 35 359 на 22; з) 5 718 на 103; и) 27 260 на 40; к) 25 1998 на 62.

147*. Докажите, что а 561 º а (mod 11).

148*. Если каноническое разложение натурального числа п не содержит множителей 2 и 5, то 12-я степень этого числа оканчивается цифрой 1. Докажите.

149*. Докажите, что 2 64 º 16 (mod 360).

150*. Докажите: если (а, 65) =1 , (b, 65) =1, то a 12 – b 12 делится без остатка на 65.

Глава 3. АРИФМЕТИЧЕСКИЕ ПРИЛОЖЕНИЯ

ТЕОРИИ ЧИСЛОВЫХ СРАВНЕНИЙ

§ 8. СИСТЕМАТИЧЕСКИЕ ЧИСЛА

ОСНОВНЫЕ СВЕДЕНИЯ ИЗ ТЕОРИИ

1. ЦЕЛЫЕ СИСТЕМАТИЧЕСКИЕ ЧИСЛА

8. 1. Определение 1.

Системой счисления называется всякий способ записи чисел. Знаки, с помощью которых записывают эти числа, называют цифрами.

8. 2. Определение 2.

Целым неотрицательным систематическим числом, записанным в t -ичной позиционной системе счисления, называется число n вида

, где a i (i = 0,1, 2,…, k ) – целые неотрицательные числа – цифры , причём 0 £ a i £ t – 1, t – основание системы счисления, t ÎN, t > 1.

Например, запись числа в 7-ричной системе имеет вид: (5603) 7 = 5 ×7 3 + 6×7 2 + 0×7 1 + 3. Здесь a i – это 5, 6, 0, 3 – цифры; все они удовлетворяют условию: 0 £ a i £ 6. При t =10 говорят: число n записано в десятичной системе счисления, причём индекс t= 10не пишут.

8. 3. Теорема 1.

Всякое целое неотрицательное число может быть представлено, причём единственным образом, в виде систематического числа по любому основанию t, где t Î N, t > 1.

Пример: (1 3 9) 10 = (3 5 1) 6 = (1 0 2 4) 5 = …

8. 4. Отметим, что:

1) приписывание к систематическому числу нулей слева не изменяет этого числа:

(3 4) 5 = (0 3 4) 5 .

2) приписывание к систематическому числу s нулей справа равносильно умножению этого числа на t s : (3 4) 5 = 3×5 1 + 4; (3 4 0 0) 5 = 3×5 3 + 4×5 2 + 0×5 1 + 0 = 5 2 ×(3×5 1 + 4).

8. 5. Алгоритм перевода числа, записанного в t -ичной системе, в десятичную:

Пример: (287) 12 = 2×12 2 + 8×12 1 +7×12 0 = 2×144 + 8×12 + 7 = 288 + 96 +7 = (391) 10 .

8. 6. Алгоритм перевода числа, записанного в десятичной системе, в t -ичную:

Пример: (3 9 1) 10 = (х ) 12 . Найти х.

8. 7. Действия над систематическими числами

2. СИСТЕМАТИЧЕСКИЕ ДРОБИ

8. 8. Определение 3.

Конечной t-ичной систематической дробью в системе счисления с основанием t называется число вида

где c 0 ÎZ , с i – цифры – целые неотрицательные числа , причём 0 £ с i £ t – 1, t Î N, t > 1, k Î N .

Обозначение: a = (c 0 , с 1 с 2 …с k ) t . При t = 10 дробь называется десятичной .

8. 9. Следствие 1.

Всякая конечная систематическая дробь есть рациональное число, которое можно представить в виде , где а Î Z, b Î N.

Пример. a = (3 1, 2 4) 6 = 3×6 + 1 + =19 + – рациональное число. Обратное утверждение, вообще говоря, неверно. Например, дробь нельзя преобразовать в конечную систематическую (десятичную) дробь.

8.10. Определение 4.

Бесконечной t-ичной положительной систематической дробью в системе счисления с основанием t называется число вида

, где с 0 Î N , с i (i =1, 2, …, к , …) – цифры – целые неотрицательные числа , причём 0 £ с i £ t –1, t ÎN, t > 1, k ÎN .

Обозначение: a = (с 0 , с 1 с 2 … с k …) t . При t =10 дробь называется десятичной .

8.11. Определение 5.

Возможны три вида бесконечных систематических дробей:

I a = (с 0 , ) t = = t , где = = = … В этом случае число a называется бесконечной чисто периодической дробью, (с 1 с 2 … с k ) – периодом , k– количество цифр в периоде – длиной периода.

II a = .

В этом случае число a называется бесконечной смешанной периодической дробью, – предпериодом , () – периодом , k – количество цифр в периоде – длиной периода, l – количество цифр между целой частью и первым периодом – длиной предпериода.

III a = (с 0 , с 1 с 2 … с k …) t . В этом случае число a называется бесконечной непериодической дробью.

ТИПОВЫЕ ЗАДАЧИ

1. Число (а ) 5 = (2 1 4 3) 5 , заданное в 5–ричной системе, перевести в 7-ричную систему, то есть найти х , если (2 1 4 3) 5 = (х ) 7 .

Решение.

1) Преобразуем данное число (2 1 4 3) 5 в число (у ) 10 , записанное в десятичной системе:

2. Выполните действия:

1) (7) 8 + (5) 8 ; 2) (7) 8 × (5) 8 ; 3) (3 6 4 2) 6 + (4 3 5 1) 6 ;

4) (5 2 3 4) 7 – (2 3 5 1) 7 ; 5) (4 2 3) 5 × (3 2) 5 ; 6) (3 0 1 4 1) 5: (4 2 3) 5 .

Решение.

1) (7) 8 + (5) 8 = (7) 10 + (5) 10 = (12) 10 = 1×8 + 4 = (1 4) 8 ;

2) (7) 8 × (5) 8 = (7) 10 × (5) 10 = (35) 10 = 4×8 + 3 = (4 3) 8 ;

6) (3 0 1 4 1) 5 | (4 2 3) 5

2 3 2 4 (3 2) 5

1 4 0 1 Ответ: 1) (1 4) 8 ; 2) (4 3) 8 ; 3) (1 2 4 3 3) 6 ; 4) (2 5 5 3) 7 ;

(0) 5 5) (3 0 1 4 1) 5 ; 6) (3 2) 5 .

УПРАЖНЕНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ

151. Числа, заданные в t -ичной системе, переведите в десятичную систему:

а) (2 3 5) 7 ; б) (2 4 3 1) 5 ; в) (1 0 0 1 0 1) 2 ; г) (1 3 ) 15 ;

д) (2 7) 11 ; е) (3 2 5 4) 6 ; ж) (1 5 0 1 3) 8 ; з) (1 1 0 1 1 0 0 1) 2 ;

и) (7 6 2) 8 ; к) (1 1 1 1) 20 .

152. Числа. заданные в десятичной системе, переведите в t -ичную систему. Сделайте проверку.

а) (1 3 2) 10 = (х ) 7 ; б) (2 9 8) 10 = (х ) 5 ; в) (3 7) 10 = (х ) 2 ; г) (3 2 4 5) 10 = (х ) 6 ;

д) (4 4 4 4) 10 = (х ) 3 ; е) (5 6 3) 10 = (х ) 12 ; ж) (5 0 0) 10 = (х ) 8 ; з) (6 0 0) 10 = (х ) 2 ;

и)(1 0 0 1 5) 10 =(х ) 20 ; к) (9 2 5) 10 = (х ) 8 ; л) (6 3 3) 10 = (х ) 15 ; м) (1 4 3) 10 = (х ) 2 .

153. Числа, заданные в t -ичной системе, переведите в q -ичную систему (путём перехода через десятичную систему).

а) (3 7) 8 = (х ) 3 ; б) (1 1 0 1 1 0) 2 = (х ) 5 ; в) ( 6 2) 11 = (х ) 4 ;

г) (4 ) 12 = (х ) 9 . д) (3 3 1 3 1) 5 = (х ) 12 .

154. а) Как изменится число (1 2 3) 5 , если к нему справа приписать нуль?

б) Как изменится число (5 7 6) 8 , если к нему справа приписать два нуля?

155. Выполните действия:

а) (3 0 2 1) 4 + (1 2 3 3) 4 ; б) (2 6 5 4) 8 + (7 5 4 3) 8 ; в) (1 0 1 1 0 1) 2 +(1 1 0 1 10) 2 ;

г) (5 2 4 7) 9 + (1 3 7 6) 9 ; д) (4 7 6) 9 – (2 8 7) 9 ; е) (2 4 5 3) 7 – (1 6 4 5) 7 ;

ж) (8 3) 12 – (5 7 9) 12 ; з) (1 7 5) 11 – ( 6) 11 ; и) (3 6 4 0 1) 7 – (2 6 6 6 3) 7 ;

к) (1 0 0 1 0) 2 × (1 1 0 1) 2 ; л) (7 4 1) 8 × (2 6) 8 ; м) (5 3 7 2) 8 × (2 4 6) 8 ;

н) (3 3 2 1) 4 × (2 3 0) 4 ; о) (1 0 2 2 2 2) 3: (1 2 2) 3 ; п) (2 1 0 3 2) 4: (3 2 3) 4 ;

р) (2 6 1 7 4) 8: (5 4 6) 8 ; с) (4 3 2 0 1) 5: (2 1 4) 5 ; т)(1 1 0 1 0 0 1 0) 2:(1 0 1 0 1) 2

у) (1 1 0 1 1 0) 2: (1 1 1) 2 ; ф) (1 1 1 0) 6: (2 1 5) 6 ; х)(3 2 3 8 2 2 1 7 0) 9:(7 6 4 2) 9 .

ц) (1 6 3 5) 8 + (7 6 4) 8 ; ч) (1 1 1 1) 3 – (2 1 2) 3 ; ш)(1 2 7) 12 +(9 1 3 5 ) 12b" × b 1 Тогда:

I Если знаменатель b = b" (содержит только "2" и / или "5"), – то дробь преобразуется в конечную десятичную дробь. Количество десятичных знаков равно наименьшему натуральному числу l l º 0(mod b ").

II Если знаменатель b = b 1 (не содержит "2" и "5"), – то дробь преобразуется в бесконечную чисто периодическую равна наименьшему натуральному числу k , удовлетворяющему сравнению 10 k º 1(mod b 1).

III Если знаменатель b = b" × b 1 (содержит "2" и / или"5", а также иные простые множители), – то дробь преобразуется в бесконечную смешанную периодическую деся-

тичную дробь.

Длина периода равна наименьшему натуральному числу k , удовлетворяющему сравнению 10 k º 1(mod b 1 ).

Длина предпериода равна наименьшему натуральному числу l , удовлетворяющему сравнению 10 l º 0(mod b ").

9. 2. Выводы.

9. 3. Отметим, что:

рациональным числом является всякая конечная десятичная дробь или бесконечная периодическая десятичная дробь;

иррациональным числом является всякая бесконечная непериодическая десятичная дробь.

ТИПОВЫЕ ЗАДАЧИ

1. Данные обыкновенные дроби, записанные в десятичной системе, преобразовать в

десятичные, предварительно определив вид искомой дроби (конечная или бесконечная; периодическая или непериодическая; если – периодическая, то чисто периодическая или смешанная периодическая); в последних случаях – предварительно найти число k – длину периода и число l – длину предпериода. 1) ; 2) ; 3) .

Решение.

1) У дроби = знаменатель – число b = 80 = 2 4 × 5 содержит только "2" и "5". Поэтому данная дробь преобразуется в конечную десятичную дробь. Количество десятичных знаков l наим определяется из условия: 10 l º0(mod80):

2) У дроби = знаменатель – число b = 27 = 3 3 не содержит "2" и "5". Поэтому данная дробь преобразуется в бесконечную чисто периодическую десятичную дробь. Длина периода k наим определяется из условия: 10 k º1(mod27):

3) У дроби = знаменатель – число b = 24 = 2 3 ×3, то есть имеет вид: b = b" × b 1 (кроме "2" или "5" содержит и иные множители, в данном случае число 3). Поэтому данная дробь преобразуется в бесконечную смешанную периодическую десятичную дробь. Длина периода k наим определяется из условия: 10 k º1(mod3), откуда k наим = 1, то есть длина периода k = 1. Длина предпериода l наим определяется из условия: 10 l º0(mod8), откуда l наим = 3, то есть длина предпериода l = 3.

Проверка: разделим "уголком" 5 на 24 и получим: = 0, 208 (3).

Ответ: 1) 0, 0375; 2) 0, (074); 3) 0, 208 (3).

УПРАЖНЕНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ

156. Данные обыкновенные дроби, записанные в десятичной системе, преобразуйте в десятичные дроби. Если десятичная дробь - периодическая, то предварительно найдите число k - длину периода и число l - длину предпериода.

157. Данные обыкновенные дроби, записанные в десятичной системе, преобразуйте в t -ичные систематические дроби. Найдите числа k - длину периода и l - длину предпериода.

158*. В какой системе счисления число (4 6) 10 записывается теми же цифрами, но в

обратном порядке?

159*. Что больше: единица 8-го разряда в двоичной системе или единица 4-го разряда в 8-ричной системе?

§ 10. ТЕОРЕМА ПАСКАЛЯ. ПРИЗНАКИ ДЕЛИМОСТИ

ОСНОВНЫЕ СВЕДЕНИЯ ИЗ ТЕОРИИ

10. 1. Теорема Паскаля (1623 – 1662).

Даны натуральные числа: т > 1 и n, записанное в t - ичной системе:

, где a i – – цифры: a i ÎN, 0 £ a i £ t –1 (i = 0,1, 2,…, k ), t ÎN, t > 1.

Пусть n = (a k a k – 1 … a 1 a 0) 10 = a k ×10 k +a k – 1 ×10 k – 1 +…+a 1 ×10 + a 0 , m =3 и m = 9.

1) Найдём b i : по модулю m = 3по модулю m = 9

10 0 º1(mod3), т.е. b 0 =1, 10 0 º1(mod9), т.е. b 0 =1,

10 1 º1(mod3), т.е. b 1 =1, 10 1 º1(mod9), т.е. b 1 =1,

10 2 º1(mod3), т.е. b 2 =1, 10 2 º1(mod9), т.е. b

Согласно свойству сравнений №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 ) – функция Мебиуса.