Приведенная система вычетов. Вычеты. Полная и приведенная системы вычетов Приведенная система по модулю 9

Согласно свойству сравнений №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. Пришли к противоречию, следовательно предположение о существовании обратного элемента неверно.

Кольцо вычетов по модулю n обозначают или . Его мультипликативную группу, как и в общем случае групп обратимых элементов колец, обозначают ∗ × × .

Простейший случай

Чтобы понять структуру группы , можно рассмотреть частный случай , где - простое число, и обобщить его. Рассмотрим простейший случай, когда , то есть .

Теорема: - циклическая группа.

Пример : Рассмотрим группу

= {1,2,4,5,7,8} Генератором группы является число 2. ≡ ≡ ≡ ≡ ≡ ≡ Как видим, любой элемент группы может быть представлен в виде , где ≤ℓφ . То есть группа - циклическая.

Общий случай

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

Примеры: 2 11 ; 8 - примитивный корень по модулю 11 ; 3 не является примитивным корнем по модулю 11 .

В случае целого модуля определение такое же.

Структуру группы определяет следующая теорема: Если p - нечётное простое число и l - целое положительное, то существуют примитивные корни по модулю , то есть - циклическая группа.

Пример

Приведённая система вычетов по модулю состоит из классов вычетов: . Относительно определённого для классов вычетов умножения они образуют группу, причём и взаимно обратны (то есть ⋅ ), а и обратны сами себе.

Структура группы

Запись означает «циклическая группа порядка n».

Структура группы (Z/ n Z) ×

	×	φ	λ	Генератор группы			×	φ	λ	Генератор группы			×	φ	λ	Генератор группы			×	φ	λ	Генератор группы
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.

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

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

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

• - см. Приведённая масса...

  Физическая энциклопедия

• - условная характеристика распределения масс в движущейся механич. или смешанной системе, зависящая от физ. параметров системы и от закона её движения...

  Физическая энциклопедия

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

  Математическая энциклопедия

• - сумма полезной площади квартирного жилого дома, а также площадей лоджий, веранд, балконов с соответствующими понижающими коэффициентами - обща приведена площ - přepočtená užitková plocha - Gesamtfläche - fajlagos alapterület - хөрвүүлсэн...

  Строительный словарь

• - См. Коэффициент пористости пород...
• - отношение объема пор горной породы к объему скелета горной породы, выражаемое обычно в долях единицы...

  Словарь по гидрогеологии и инженерной геологии

• - см. коэффициент пористости...

  Толковый словарь по почвоведению

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

  Большой энциклопедический политехнический словарь

• - Налог, взыскиваемый у источника с дивидендов или другого дохода, получаемого нерезидентом страны...

  Финансовый словарь

• - Налог, взыскиваемый у источника с дивидендов или другого дохода, получаемого не резидентом страны...

  Словарь бизнес терминов

• - по модулю m, любая совокупность целых чисел, содержащая по одному числу из каждого класса чисел по модулю m . В качестве П. с. в. чаще всего применяется система наименьших положительных вычетов 0, 1, 2,.....
• - условная характеристика распределения масс в движущейся механической или смешанной системе, зависящая от физических параметров системы и от закона её движения...

  Большая Советская энциклопедия

• - ПРИВЕДЕННАЯ масса - условная характеристика распределения масс в движущейся механической или смешанной системе, зависящая от физических параметров системы и от закона ее движения...

  Большой энциклопедический словарь

• - общий, весь, совокупный,...

  Словарь синонимов

• - прил., кол-во синонимов: 1 чистый...

  Словарь синонимов

"Приведённая система вычетов" в книгах

Какова приведенная стоимость ключевой сферы компетенции?

Из книги Невесомое богатство. Определите стоимость вашей компании в экономике нематериальных активов автора Тиссен Рене

Какова приведенная стоимость ключевой сферы компетенции? Исходя из рассмотренного выше, мы можем сказать, что приведенная стоимость ключевой сферы компетенции рассчитывается перемножением всех показателей за определенное время с учетом затрат на привлечение

Чистая приведенная стоимость (NPV)

Из книги МВА за 10 дней. Самое важное из программ ведущих бизнес-школ мира автора Силбигер Стивен

Чистая приведенная стоимость (NPV) Анализ приведенной стоимости (NPV) помогает посчитать, сколько работнику нужно вложить, чтобы через 30 лет получать достойную пенсию, но этот анализ бесполезен при оценке текущих инвестиций и проектов. Инвестиции необходимо оценивать в

УЧЕТ УДЕРЖАНИЙ И ВЫЧЕТОВ ИЗ ЗАРАБОТНОЙ ПЛАТЫ

Из книги Бухгалтерский учет автора Мельников Илья

УЧЕТ УДЕРЖАНИЙ И ВЫЧЕТОВ ИЗ ЗАРАБОТНОЙ ПЛАТЫ В соответствии с законодательством из заработной платы работников производятся следующие удержания:– подоходный налог (государственный налог, объект обложения – заработную плата);– погашение задолженности по ранее

10.6. Учет удержаний и вычетов из заработной платы

Из книги Бухгалтерский учет в сельском хозяйстве автора Бычкова Светлана Михайловна

10.6. Учет удержаний и вычетов из заработной платы Из заработной платы работников предприятия производятся определенные удержания, которые подразделяются следующим образом: обязательные удержания (налог на доходы физических лиц, удержания по исполнительным листам);

Из книги Нематериальные активы: бухгалтерский и налоговый учет автора Захарьин В Р

<...>

4.1. Общие вопросы предоставления социальных налоговых вычетов

автора Макурова Татьяна

4.1. Общие вопросы предоставления социальных налоговых вычетов Социальные налоговые вычеты (ст.219 НК) так же, как и имущественный вычет на приобретение жилья, означают уменьшение налогооблагаемой базы на величину произведенных социальных расходов с учетом законодательно

4.3. Особенности предоставления образовательных вычетов

Из книги Самоучитель по налогам на доходы физлиц автора Макурова Татьяна

4.3. Особенности предоставления образовательных вычетов 142) Какие расходы могут быть приняты к вычету на обучение? Каковы лимиты образовательных вычетов?К социальному налоговому вычету на образование принимаются: расходы в сумме, уплаченной налогоплательщиком в

3.4. Количественная оценка и периодичность возникновения и применения налоговых вычетов

Из книги Налоговая нагрузка предприятия: анализ, расчет, управление автора Чипуренко Елена Викторовна

3.4. Количественная оценка и периодичность возникновения и применения налоговых вычетов 3.4.1. НДС как потенциальный налоговый вычет При исчислении НДС суммы налоговых вычетов определяются только в соответствии с данными регистров налогового учета – книг покупок. При

Полная система вычетов

Из книги Большая Советская Энциклопедия (ПО) автора БСЭ

Приведённая масса

БСЭ

Приведённая система вычетов

Из книги Большая Советская Энциклопедия (ПР) автора БСЭ

88. Структурная и приведённая формы системы одновременных уравнений. Идентификация модели

Из книги Ответы на экзаменационные билеты по эконометрике автора Яковлева Ангелина Витальевна

88. Структурная и приведённая формы системы одновременных уравнений. Идентификация модели Структурными уравнениями называются уравнения, из которых состоит исходная система одновременных уравнений. В данном случае система имеет структурную форму.Структурная форма

Из книги Новое в Налоговом кодексе: комментарий к изменениям, вступившим в силу в 2008 году автора Зрелов Александр Павлович

Статья 172. Порядок применения налоговых вычетов Комментарий к статье 172В тексте абз.1 п.2 комментируемой статьи отменено условие, предписывающее производить исчисления суммы налога исходя из балансовой стоимости имущества (с учетом его переоценок и амортизации, которые

автора Автор неизвестен

Статья 172. Порядок применения налоговых вычетов 1. Налоговые вычеты, предусмотренные статьей 171 настоящего Кодекса, производятся на основании счетов-фактур, выставленных продавцами при приобретении налогоплательщиком товаров (работ, услуг), имущественных прав,

Из книги Налоговый кодекс Российской Федерации. Части первая и вторая. Текст с изменениями и дополнениями на 1 октября 2009 г. автора Автор неизвестен

Статья 201. Порядок применения налоговых вычетов 1. Налоговые вычеты, предусмотренные пунктами 1 – 4 статьи 200 настоящего Кодекса, производятся на основании расчетных документов и счетов-фактур, выставленных продавцами при приобретении налогоплательщиком подакцизных

В предыдущем пункте было отмечено, что отношение  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 ) – функция Мебиуса.