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

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

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

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

Обозначение класса чисел, имеющих остаток r: полная и приведённая системы вычетов - student2.ru .

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

6. 2. Свойства множества классов вычетов полная и приведённая системы вычетов - student2.ru по модулю т:

1) всего по модулю т будет т классоввычетов: Zт = { полная и приведённая системы вычетов - student2.ru , полная и приведённая системы вычетов - student2.ru , полная и приведённая системы вычетов - student2.ru , … , полная и приведённая системы вычетов - student2.ru };

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

3) "а Î полная и приведённая системы вычетов - student2.ru : а º r (mod m);

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

5) "а Î полная и приведённая системы вычетов - student2.ru , "b Î полная и приведённая системы вычетов - student2.ru : а полная и приведённая системы вычетов - student2.ru 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, … , хт} – полная система вычетов по модулю т, то полная и приведённая системы вычетов - student2.ru

полная и приведённая системы вычетов - student2.ru .

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

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

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

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

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

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

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

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

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

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

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

2) полная и приведённая системы вычетов - student2.ru : полная и приведённая системы вычетов - student2.ru .

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

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

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

Множество классов вычетов, взаимно простых с модулем m=10: { полная и приведённая системы вычетов - student2.ru , полная и приведённая системы вычетов - student2.ru , полная и приведённая системы вычетов - student2.ru , полная и приведённая системы вычетов - student2.ru }(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,…, полная и приведённая системы вычетов - student2.ru } – приведённая система вычетов по модулю т и

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

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

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

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

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

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

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

6.14. Теорема 4.

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

< Zт , +, · > = < { полная и приведённая системы вычетов - student2.ru , полная и приведённая системы вычетов - student2.ru , полная и приведённая системы вычетов - student2.ru ,…, полная и приведённая системы вычетов - student2.ru }, +, · > – кольцо.

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

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};

3) например, {10, – 7, 21, 49, – 4, 15, 25, – 1, 0}; 4) {– 4, – 3, – 2, – 1, 0, 1, 2, 3, 4}.

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, 20, 21, 22, ... , 29 } полную систему вычетов по модулю 11 ?

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

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

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

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

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

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

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

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

Если аÎZ, тÎN, т >1 и (а; т) = 1, – то полная и приведённая системы вычетов - student2.ru . (13)

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

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

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

Пример. Пусть а = 3, р = 5, где 3 не полная и приведённая системы вычетов - student2.ru 5. Тогда полная и приведённая системы вычетов - student2.ru или полная и приведённая системы вычетов - student2.ru .

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

Для любого простого числа р и произвольного числа аÎZ имеет место сравнение полная и приведённая системы вычетов - student2.ru (15)

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

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

Решение.

1) Так как (38; 35) = 1, то по теореме Эйлера полная и приведённая системы вычетов - student2.ru ; j(35) = 24, значит,

полная и приведённая системы вычетов - student2.ru (1).

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

полная и приведённая системы вычетов - student2.ru (2) .

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

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

Решение.

1) Так как (a; m) = (4; 25) = 1, то по теореме Эйлера полная и приведённая системы вычетов - student2.ru , j(25) = 20, поэтому полная и приведённая системы вычетов - student2.ru .

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

3) При п = 1: полная и приведённая системы вычетов - student2.ru ;

при п = 2: полная и приведённая системы вычетов - student2.ru ;

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

при п = 4: полная и приведённая системы вычетов - student2.ru ;

при п = 5: полная и приведённая системы вычетов - student2.ru ;

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

при п = 10: полная и приведённая системы вычетов - student2.ru .

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

Ответ: полная и приведённая системы вычетов - student2.ru .

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

141. По теореме Эйлера полная и приведённая системы вычетов - student2.ru . При а = 3, т = 6 имеем: полная и приведённая системы вычетов - student2.ru .

Так как j(6) = 2, то 3 2º1(mod 6), или 9º1(mod 6), Тогда, по лемме, (9 – 1) полная и приведённая системы вычетов - student2.ru 6 или 8 полная и приведённая системы вычетов - student2.ru 6 (нацело!?). Где ошибка?

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

143. Докажите, что а) 116 + 316 + 716 + 916 º 4 (mod 10);

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

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

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

д) полная и приведённая системы вычетов - student2.ru ; е) полная и приведённая системы вычетов - student2.ru ; ж) полная и приведённая системы вычетов - student2.ru ; з) полная и приведённая системы вычетов - student2.ru .

и) полная и приведённая системы вычетов - student2.ru ; к) полная и приведённая системы вычетов - student2.ru ; л) полная и приведённая системы вычетов - student2.ru ; м) полная и приведённая системы вычетов - student2.ru .

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

а) 7100 на 11; б) 9900 на 5; в) 5176 на 7; г) 21999 на 5; д) 8377 на 5;

е) 26 57 на 35; ж) 35 359 на 22; з) 5718 на 103; и) 27260 на 40; к) 251998 на 62.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Например, запись числа в 7-ричной системе имеет вид: (5603)7 = 5 ×73 + 6×72 + 0×71 + 3. Здесь ai – это 5, 6, 0, 3 – цифры; все они удовлетворяют условию: 0 £ ai £ 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×51 + 4; (3 4 0 0)5 = 3×53 + 4×52 + 0×51 + 0 = 52×(3×51 + 4).

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

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

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

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

Находим остатки от деления на основание системы t = 12: 1) данного числа 391 на 12, получим r1 = 7 ; 2) первого частного 32 на 12, получим r2 = 8 ; 3) второго частного 2 на 12, получим r3 = 2 ; Искомое число х составляется из остатков, записываемых последовательно, начиная с последнего: х = (2 8 7)12 . 391 36 31 24  
32 24  
2  
8 = r2 0 0
7 = r1 2 = r3

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

осуществляются с помощью таблиц сложения и умножения размером t ´ t. Например, при t = 2 таблицы имеют вид: + 0 1   ´ 0 1
0 1 1 10 0 0 0 1

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

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

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

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

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

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

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

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

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

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

полная и приведённая системы вычетов - student2.ru , где с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 , полная и приведённая системы вычетов - student2.ru полная и приведённая системы вычетов - student2.ru полная и приведённая системы вычетов - student2.ru полная и приведённая системы вычетов - student2.ru )t = = полная и приведённая системы вычетов - student2.ru t , где полная и приведённая системы вычетов - student2.ru = полная и приведённая системы вычетов - student2.ru = полная и приведённая системы вычетов - student2.ru = … В этом случае число a называется бесконечной чисто периодической дробью, (с1 с2 … сk) – периодом, k– количество цифр в периоде – длиной периода.

II a = полная и приведённая системы вычетов - student2.ru .

В этом случае число a называется бесконечной смешанной периодической дробью, полная и приведённая системы вычетов - student2.ru – предпериодом, ( полная и приведённая системы вычетов - student2.ru ) – периодом, 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 4 3) 5 = 2×53 +1×52 + 4×5 +3 = = 2×125 +1×25 + 4×5 +3 =250 +25 + 20+3 = (2 9 8) 10. 2) Преобразуем полученное число (у)10 в семеричную систему (х)7 (см. справа): Ответ: (2 1 4 3) 5 = (6 0 4) 7. 298 28 18 14 4 = r1    
42 42  
6  
0 = r2   0 0 6 = r3

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 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 полная и приведённая системы вычетов - student2.ru )15;

д) (2 полная и приведённая системы вычетов - student2.ru 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; в) ( полная и приведённая системы вычетов - student2.ru 6 2) 11 = (х) 4 ;

г) (4 полная и приведённая системы вычетов - student2.ru полная и приведённая системы вычетов - student2.ru )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 полная и приведённая системы вычетов - student2.ru 3) 12 – (5 7 9) 12; з) (1 7 5) 11 – ( полная и приведённая системы вычетов - student2.ru 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 полная и приведённая системы вычетов - student2.ru 2 полная и приведённая системы вычетов - student2.ru 7)12+(9 1 3 5 полная и приведённая системы вычетов - student2.ru )12

щ) (1 6 3 5) 8 × (7 6 4) 8; э) (9 5 7 полная и приведённая системы вычетов - student2.ru 2) 11 × (3 2) 11; ю)(2 полная и приведённая системы вычетов - student2.ru 1 2 7 4 5)11 : (3 полная и приведённая системы вычетов - student2.ru 1)11

я) (1 0 0 0 1 0 1 1 0 0 1) 2 × (1 1 1 0 0 0 1) 2 .

§ 9. ПЕРЕХОД ОТ РАЦИОНАЛЬНОГО ЧИСЛА ВИДА полная и приведённая системы вычетов - student2.ru

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

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

9. 1. Установим условия, при которых число вида полная и приведённая системы вычетов - student2.ru , где а, b Î N, (а, b) =1, а < b, преобразуетсяв тот или иной вид систематической дроби (для случая, когда t = 10, то есть в десятичной системе счисления).

Пусть t = 10 = 2×5, а в числе полная и приведённая системы вычетов - student2.ru знаменатель b имеет вид:

полная и приведённая системы вычетов - student2.ru (qi – простые числа), то есть b = b' × b1 Тогда:

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

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

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

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

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

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

9. 2. Выводы.

a к о н е ч н а я д е с я т и ч н а я д р о б ь полная и приведённая системы вычетов - student2.ru полная и приведённая системы вычетов - student2.ru рацион. число полная и приведённая системы вычетов - student2.ru   иррацион. число
бесконечная десятичная дробь полная и приведённая системы вычетов - student2.ru 1) чисто периодическая дробь 2) смешанная периодич. дробь 3) непериодическая дробь
             

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

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

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

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

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

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

Решение.

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

Имеем:10 1º10(mod80), 10 2= 100 º20(mod80), 10 3º200 º 40(mod80), 10 4º400 º 0(mod80). Следовательно, l наим = 4, то есть искомая десятичная дробь будет иметь 4 десятичных знака. Проверка: разделим "уголком" 3 на 80 и получим: полная и приведённая системы вычетов - student2.ru = 0, 0375.

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

Имеем: 10 1º10(mod27), 10 2º100–81º19(mod27), 10 3º190 º190 – 7×27 º º 190 – 189 º 1(mod27). Следовательно, k наим = 3, то есть в искомой десятичной дроби будет период длиной k = 3. Проверка: разделим "уголком" 2 на 27 и получим: полная и приведённая системы вычетов - student2.ru = 0, (074).

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

Проверка: разделим "уголком" 5 на 24 и получим: полная и приведённая системы вычетов - student2.ru = 0, 208 (3).

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

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

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

полная и приведённая системы вычетов - student2.ru

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

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

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

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

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

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

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

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

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

Пусть полная и приведённая системы вычетов - student2.ru полная и приведённая системы вычетов - student2.ru

Итак: из равенства (*) в теореме Паскаля следует, что число n и число полная и приведённая системы вычетов - student2.ru сравнимы по модулю т (а значит – равноостаточны при делении на т). Отсюда, в частности, вытекает, что если полная и приведённая системы вычетов - student2.ru делится на т без остатка, то и n делится на т без остатка. Поэтому имеет место следствие:

10. 2. Следствие.

Для того, чтобы число n делилось без остатка на число т, необходимо и достаточно, чтобы сумма полная и приведённая системы вычетов - student2.ru делилась без остатка на т:

полная и приведённая системы вычетов - student2.ru (16)

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

1. Установите в десятичной системе счисления признаки делимости на 3, на 9 и на 11.

1) Признаки делимости на 3 и на 9.

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

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

100 º1(mod3), т.е. b0 =1, 100 º1(mod9), т.е. b0 =1,

101 º1(mod3), т.е. b1 =1, 101 º1(mod9), т.е. b1 =1,

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

Наши рекомендации