Полная и приведенная система вычетов примеры. Приведённая система вычетов
ОСНОВНЫЕ СВЕДЕНИЯ ИЗ ТЕОРИИ
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 ;
3) (3 6 4 2) 6 + (4 3 5 1) 6 (1 2 4 3 3) 6 | Примечание: | 4+5 = 9 = 1×6+3, 3 пишем, 1 переходит в следующий разряд, 6+3+1=10 =1×6+4, 4 пишем, 1 переходит в следующий разряд, 3+4+1= 8 = 1×6+2, 2 пишем, 1 переходит в следующий разряд. |
4) (5 2 3 4) 7 – (2 3 5 1) 7 (2 5 5 3) 7 | Примечание: | "занимаем" единицу высшего разряда, т. е. "1" = 1×7: (3 + 1×7) – 5 = 10 – 5 = 5, (1 + 1×7) – 3 = 8 – 3 = 5, |
5) (4 2 3) 5 ´ (3 2) 5 (1 4 0 1) 5 + (2 3 2 4) 5__ (3 0 1 4 1) 5 | Примечание: | При умножении на 2: 3 ×2 = 6 = 1×5 + 1, 1 пишем, 1 переходит в следующий разряд, 2 ×2 +1=5 = 1×5 +0, 0 пишем, 1 переходит в следующий разряд, 2 ×4 +1=9 = 1×5 +4, 4 пишем, 1 переходит в следующий разряд, При умножении на 3: 3 ×3 = 9 = 1×5 + 4, 4 пишем, 1 переходит в следующий разряд, 3 ×2 +1=7 = 1×5 +2, 2 пишем, 1 переходит в следующий разряд, 3 ×4 +1=13=2×5 +3, 3 пишем, 2 переходит в следующий разряд. |
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
Кольцо вычетов по модулю n обозначают или . Его мультипликативную группу, как и в общем случае групп обратимых элементов колец, обозначают ∗ × × .
Простейший случай
Чтобы понять структуру группы , можно рассмотреть частный случай , где - простое число, и обобщить его. Рассмотрим простейший случай, когда , то есть .
Теорема: - циклическая группа.
Пример : Рассмотрим группу
= {1,2,4,5,7,8} Генератором группы является число 2. ≡ ≡ ≡ ≡ ≡ ≡ Как видим, любой элемент группы может быть представлен в виде , где ≤ℓφ . То есть группа - циклическая.Общий случай
Для рассмотрения общего случая необходимо определение примитивного корня . Примитивный корень по простому модулю - это число, которое вместе со своим классом вычетов порождает группу .
Примеры: 2 11 ; 8 - примитивный корень по модулю 11 ; 3 не является примитивным корнем по модулю 11 .В случае целого модуля определение такое же.
Структуру группы определяет следующая теорема: Если p - нечётное простое число и l - целое положительное, то существуют примитивные корни по модулю , то есть - циклическая группа.
Пример
Приведённая система вычетов по модулю состоит из классов вычетов: . Относительно определённого для классов вычетов умножения они образуют группу, причём и взаимно обратны (то есть ⋅ ), а и обратны сами себе.
Структура группы
Запись означает «циклическая группа порядка n».
× | φ | λ | Генератор группы | × | φ | λ | Генератор группы | × | φ | λ | Генератор группы | × | φ | λ | Генератор группы | |||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
1 | C 1 | 1 | 1 | 0 | 33 | C 2 ×C 10 | 20 | 10 | 2, 10 | 65 | C 4 ×C 12 | 48 | 12 | 2, 12 | 97 | C 96 | 96 | 96 | 5 | |||
2 | C 1 | 1 | 1 | 1 | 34 | C 16 | 16 | 16 | 3 | 66 | C 2 ×C 10 | 20 | 10 | 5, 7 | 98 | C 42 | 42 | 42 | 3 | |||
3 | C 2 | 2 | 2 | 2 | 35 | C 2 ×C 12 | 24 | 12 | 2, 6 | 67 | C 66 | 66 | 66 | 2 | 99 | C 2 ×C 30 | 60 | 30 | 2, 5 | |||
4 | C 2 | 2 | 2 | 3 | 36 | C 2 ×C 6 | 12 | 6 | 5, 19 | 68 | C 2 ×C 16 | 32 | 16 | 3, 67 | 100 | C 2 ×C 20 | 40 | 20 | 3, 99 | |||
5 | C 4 | 4 | 4 | 2 | 37 | C 36 | 36 | 36 | 2 | 69 | C 2 ×C 22 | 44 | 22 | 2, 68 | 101 | C 100 | 100 | 100 | 2 | |||
6 | C 2 | 2 | 2 | 5 | 38 | C 18 | 18 | 18 | 3 | 70 | C 2 ×C 12 | 24 | 12 | 3, 69 | 102 | C 2 ×C 16 | 32 | 16 | 5, 101 | |||
7 | C 6 | 6 | 6 | 3 | 39 | C 2 ×C 12 | 24 | 12 | 2, 38 | 71 | C 70 | 70 | 70 | 7 | 103 | C 102 | 102 | 102 | 5 | |||
8 | C 2 ×C 2 | 4 | 2 | 3, 5 | 40 | C 2 ×C 2 ×C 4 | 16 | 4 | 3, 11, 39 | 72 | C 2 ×C 2 ×C 6 | 24 | 6 | 5, 17, 19 | 104 | C 2 ×C 2 ×C 12 | 48 | 12 | 3, 5, 103 | |||
9 | C 6 | 6 | 6 | 2 | 41 | C 40 | 40 | 40 | 6 | 73 | C 72 | 72 | 72 | 5 | 105 | C 2 ×C 2 ×C 12 | 48 | 12 | 2, 29, 41 | |||
10 | C 4 | 4 | 4 | 3 | 42 | C 2 ×C 6 | 12 | 6 | 5, 13 | 74 | C 36 | 36 | 36 | 5 | 106 | C 52 | 52 | 52 | 3 | |||
11 | C 10 | 10 | 10 | 2 | 43 | C 42 | 42 | 42 | 3 | 75 | C 2 ×C 20 | 40 | 20 | 2, 74 | 107 | C 106 | 106 | 106 | 2 | |||
12 | C 2 ×C 2 | 4 | 2 | 5, 7 | 44 | C 2 ×C 10 | 20 | 10 | 3, 43 | 76 | C 2 ×C 18 | 36 | 18 | 3, 37 | 108 | C 2 ×C 18 | 36 | 18 | 5, 107 | |||
13 | C 12 | 12 | 12 | 2 | 45 | C 2 ×C 12 | 24 | 12 | 2, 44 | 77 | C 2 ×C 30 | 60 | 30 | 2, 76 | 109 | C 108 | 108 | 108 | 6 | |||
14 | C 6 | 6 | 6 | 3 | 46 | C 22 | 22 | 22 | 5 | 78 | C 2 ×C 12 | 24 | 12 | 5, 7 | 110 | C 2 ×C 20 | 40 | 20 | 3, 109 | |||
15 | C 2 ×C 4 | 8 | 4 | 2, 14 | 47 | C 46 | 46 | 46 | 5 | 79 | C 78 | 78 | 78 | 3 | 111 | C 2 ×C 36 | 72 | 36 | 2, 110 | |||
16 | C 2 ×C 4 | 8 | 4 | 3, 15 | 48 | C 2 ×C 2 ×C 4 | 16 | 4 | 5, 7, 47 | 80 | C 2 ×C 4 ×C 4 | 32 | 4 | 3, 7, 79 | 112 | C 2 ×C 2 ×C 12 | 48 | 12 | 3, 5, 111 | |||
17 | C 16 | 16 | 16 | 3 | 49 | C 42 | 42 | 42 | 3 | 81 | C 54 | 54 | 54 | 2 | 113 | C 112 | 112 | 112 | 3 | |||
18 | C 6 | 6 | 6 | 5 | 50 | C 20 | 20 | 20 | 3 | 82 | C 40 | 40 | 40 | 7 | 114 | C 2 ×C 18 | 36 | 18 | 5, 37 | |||
19 | C 18 | 18 | 18 | 2 | 51 | C 2 ×C 16 | 32 | 16 | 5, 50 | 83 | C 82 | 82 | 82 | 2 | 115 | C 2 ×C 44 | 88 | 44 | 2, 114 | |||
20 | C 2 ×C 4 | 8 | 4 | 3, 19 | 52 | C 2 ×C 12 | 24 | 12 | 7, 51 | 84 | C 2 ×C 2 ×C 6 | 24 | 6 | 5, 11, 13 | 116 | C 2 ×C 28 | 56 | 28 | 3, 115 | |||
21 | C 2 ×C 6 | 12 | 6 | 2, 20 | 53 | C 52 | 52 | 52 | 2 | 85 | C 4 ×C 16 | 64 | 16 | 2, 3 | 117 | C 6 ×C 12 | 72 | 12 | 2, 17 | |||
22 | C 10 | 10 | 10 | 7 | 54 | C 18 | 18 | 18 | 5 | 86 | C 42 | 42 | 42 | 3 | 118 | C 58 | 58 | 58 | 11 | |||
23 | C 22 | 22 | 22 | 5 | 55 | C 2 ×C 20 | 40 | 20 | 2, 21 | 87 | C 2 ×C 28 | 56 | 28 | 2, 86 | 119 | C 2 ×C 48 | 96 | 48 | 3, 118 | |||
24 | C 2 ×C 2 ×C 2 | 8 | 2 | 5, 7, 13 | 56 | C 2 ×C 2 ×C 6 | 24 | 6 | 3, 13, 29 | 88 | C 2 ×C 2 ×C 10 | 40 | 10 | 3, 5, 7 | 120 | C 2 ×C 2 ×C 2 ×C 4 | 32 | 4 | 7, 11, 19, 29 | |||
25 | C 20 | 20 | 20 | 2 | 57 | C 2 ×C 18 | 36 | 18 | 2, 20 | 89 | C 88 | 88 | 88 | 3 | 121 | C 110 | 110 | 110 | 2 | |||
26 | C 12 | 12 | 12 | 7 | 58 | C 28 | 28 | 28 | 3 | 90 | C 2 ×C 12 | 24 | 12 | 7, 11 | 122 | C 60 | 60 | 60 | 7 | |||
27 | C 18 | 18 | 18 | 2 | 59 | C 58 | 58 | 58 | 2 | 91 | C 6 ×C 12 | 72 | 12 | 2, 3 | 123 | C 2 ×C 40 | 80 | 40 | 7, 83 | |||
28 | C 2 ×C 6 | 12 | 6 | 3, 13 | 60 | C 2 ×C 2 ×C 4 | 16 | 4 | 7, 11, 19 | 92 | C 2 ×C 22 | 44 | 22 | 3, 91 | 124 | C 2 ×C 30 | 60 | 30 | 3, 61 | |||
29 | C 28 | 28 | 28 | 2 | 61 | C 60 | 60 | 60 | 2 | 93 | C 2 ×C 30 | 60 | 30 | 11, 61 | 125 | C 100 | 100 | 100 | 2 | |||
30 | C 2 ×C 4 | 8 | 4 | 7, 11 | 62 | C 30 | 30 | 30 | 3 | 94 | C 46 | 46 | 46 | 5 | 126 | C 6 ×C 6 | 36 | 6 | 5, 13 | |||
31 | C 30 | 30 | 30 | 3 | 63 | C 6 ×C 6 | 36 | 6 | 2, 5 | 95 | C 2 ×C 36 | 72 | 36 | 2, 94 | 127 | C 126 | 126 | 126 | 3 | |||
32 | C 2 ×C 8 | 16 | 8 | 3, 31 | 64 | C 2 ×C 16 | 32 | 16 | 3, 63 | 96 | C 2 ×C 2 ×C 8 | 32 | 8 | 5, 17, 31 | 128 | C 2 ×C 32 | 64 | 32 | 3, 127 |
Применение
На сложности, Ферма, Хули, . Уоринг сформулировал теорему Вильсона, а Лагранж её доказал. Эйлер предположил существование примитивных корней по модулю простого числа. Гаусс это доказал. Артин выдвинул свою гипотезу о существовании и количественной оценке простых чисел, по модулю которых заданное целое число является первообразным корнем. Брауэр внес вклад в исследование проблемы существования наборов последовательных целых чисел, каждое из которых - k-ая степень по модулю p. Билхарц доказал аналог гипотезы Артина. Хули доказал гипотезу Артина с предположением справедливости расширенной гипотезы Римана в полях алгебраических чисел.
Примечания
Литература
- Айерлэнд К., Роузен М. Классическое введение в современную теорию чисел. - М. : Мир, 1987.
- Алферов А.П., Зубов А.Ю., Кузьмин А.С. Черемушкин А.В. Основы криптографии. - Москва: «Гелиос АРВ», 2002.
- Ростовцев А.Г., Маховенко Е.Б. Теоретическая криптография. - Санкт-Петербург: НПО «Профессионал», 2004.
Согласно свойству сравнений №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. Пришли к противоречию, следовательно предположение о существовании обратного элемента неверно.
В частности, будем иметь (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). В предыдущем пункте
было отмечено, что отношение 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
)
– функция Мебиуса.Вычеты. Полная и приведенная системы вычетов
Теоремы Эйлера и Ферма
Функция Эйлера.
огда: