Эскорт-услуги в Москве от Queens Palace


GOUSPO студенческий портал!

форум, учебники, лекции, и многое другое

Основы алгебры вычетов.

Тема 9. Основы алгебры вычетов.

План:

1.Понятие вычета.

2.Сравнение по модулю.

3. Свойства сравнимости

Цель. Знакомство с понятиями класса вычетов, отношением сравнимости и его свойствами.

Теоретические сведения

1. Понятие вычета.

Вычетом числа a по модулю m называется остаток от деления  a на m

Из определения видно, что вычеты связаны с делением с остатком.

Разделить натуральное число a на нату­ральное число b с остатком означает yнайти неотрицательные числа два числа q и г, причем г < b  такие, что  выполняется равенство

а = q·b + г

Так для чисел 187 и 12 соответствуют  два числа 15 и 7, такие, что 187= 15·12+7. Это равенство часто записывается в виде 187:12 = 15(ост. 7).

Напишем названия компонентов деления с остатком:

а – делимое, b- делитель, q- частное, r – остаток.

Рассмотрим  еще примеры:

а = - 12,   b = 8          ®        -12 = (- 2) · 8 + 4,                  q= -2,  r=4

а = - 324, b = - 15     ®        324 = 22 · (- 15) + 6            q=22,   r=6

a = 4,       b=10          ®        4=0·10+4                               q=0,     r=4

a = 12,     b = 4           ®        12=4·3+0                               q=4,     r=0

Число a делится нацело на b, если остаток r = 0  или,  а = qb. .Причем отношение делиться на цело обозначается .

Теорема. Если а и b делятся на с, то при любых целых k и j сумма ka + jb делится на с.

Задание 9-1. Найти такое число d ¹ 1, на которое делятся чис­ла 6п + 5 и 9л + 2. При каком значении  п. это деление возможно?

Решение. Если числа 6п + 5 и 9п + 2 делятся на d, то на d делится и разность

3(6n + 5) -  2(9п + 2) = 15 -  4 = 11

Число 11  простое число, значит  d= 11.

Не трудно установить, что п = - 21, 10, 1, 12, 23

2. Сравнение по модулю.

Числа в основном сравнивают  по величине, но их  можно сравнивать по другим признакам и свойствам. Например, по количеству цифр, по остаткам деления, по делимости на некоторое число и др.

Рассмотрим сравнение чисел на основе равенства их остатков при делении на некоторое число, что приводи к понятию вычетов. Такое сравнение называется сравнением по модулю. Не следует путать  с абсолютной величиной числа, которая так же называется модулем.  Введем форму записи остатка:

R = A mod B, где A-делимое, B- делитель, R-остаток.

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

Например, 5=15 mod 10, 3= 45 mod 7 и т.д.

При делении n (nÎZ) на g все целые числа разбиваются на g подмножеств, которые соответствуют числу, полученному в остатке. Остатки при этом будут равны:

n mod g ={0,1,2,…g-1}

Причем, каждому остатку можно поставить в соответствие множество чисел вида:

0          ® n mod g =0                        n=k g

1          ® n mod g =1                                    n=kg+1

2          ® n mod g =2                        n=kg+2

3          ® n mod g =3                        n=kg+3

g-1       ® n mod g =g-1                     n=k(g-1)

Очевидно, что любое целое число а принадлежит одному из этих g подмножеств. Причем разность любых двух чисел одного под­множества делится на g, а разность чисел из разных множеств не должна делиться на g.

Два целых числа называются сравнимыми по модулю g (g ³ 2), если их разность кратна натуральному числу,  т.е.  b) g,.

Запишем это определение символами:

а º b (mod g), если $ kÎ Zb= kg).,

Это значит, что числа а и b сравнимы по модулю g тогда и только тогда, когда они принадлежат одному подмножеству, т.е. дают одинаковые остатки при делении на g..

Например:      36 º I6 (mod l0)         –  числа 36  и 16 сравнимы по модулю 10

24 º 4 (mod 6)            -  число 24 сравнимо по модулю 6 с число 4

-26º 6 (mod 30)

Отметим разницу в записях: записей:

1. аº b (mod g ) или (а= b) (mod g ) означает сравнимость чисел по модулю (сравнение)

2. а= b (mod g ) -   означает равенство числа  a остатку от деления b на g

Отношение сравнимости рефлексивно, симметрично, транзитивно. Следовательно, оно является отношением эквивалентности.

Вычетами по модулю р называют отдельные классы эквивалентности для отношения сравнимо­сти (по модулю p)) и обозначают Zp,

Раздел математики, изучающий вычеты по модулю, называется ал­геброй вычетов (теорией вычетов, модулярной арифметикой).

3. Свойства сравненимости

1. Два числа, сравнимые с третьим по одному модулю, сравни­мы между собой:

2. Сравнения можно складывать и вычитать:

º b(mod p); cºd(mod p)) => (а ± с) º (b ± d)(mod p).

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

3.  Сравнения можно перемножать:

(a º b(mod p), с º d(mod p)) => (ас º bd(mod p)).

4. Обе части сравнения можно умножить на одно и то же целое число k:

(а º 6(mod p}) => (ak º bk(mod p)).

5. Обе части сравнения и модуль можно умножить на одно и то же число:

(а º b (mod p)) => (akºbk(mod pk)).

6. Обе части сравнения можно возвести в степень (следствие свойства 3):

(а º b (mod p)) => (аn = bn (mod p)).

Понятие сравнения ввел К.Ф.Гаусс в работе Ариф­метические исследования (1802). Алгебра вычетов возникает в тех случаях, когда рассматриваются некоторые циклически повторя­ющиеся события, например время в течение дня, повторяющееся каждые 24 часа, углы по окружности, повторяющиеся через пе­риод 2к, и т.д.

Алгебра вычетов один из тех разделов математики, которые рождались как некоторые формальные  рассуждения и только спустя годы нашли свое практи­ческое применение.

Задание 9-2. Для степени  y=2n (n–натуральное число) установить классы сравнимости. Установить зависимость последней цифры этой степени от ее показателя.

Решение и комментарии.

Как известно, натуральные степени числа 2 оканчиваются циф­рами {2, 4, 8, 6}. См. таблицу нескольких степеней числа 2.

Опреде­лим функцию, которая ставит в соответствие каждому натуральному числу п последнюю цифру числа 2я:

n 2n Последняя

цифра 2т

1 2 2
2 4 4
3 8 8
4 16 6
5 32 2
6 64 4
7 128 8
8 256 6

f: N®{2, 4, 8, 6},

Эта функция  f(n) периодична с периодом 4. Это значит, что для  целого числа  k:   f(n)=f(n+4)= f(n+4k),.

Причем справедливы так же равенства:  f(n)=f(n-4)= f(n-4k)

Последнее равенство означают, что для любого п нужно найти минимальное натуральное т, такое, что f(m) = f(m + 4k) = f(n).

Но это задача на делении с остатком числа n на  4:

n=4k+m, k- частное, т остаток.

Очевидно, последняя цифра числа 2 зависит от остатка, полученного при  делении показателя  n степени 2 n на 4.

Отразим этот факт в записи функции:  f(n)= f(n mod 4)

Из этой формулы можно установить,  если f(n mod 4)=0, то

При делении чисел на 4 nÎN, останки могут быть: 0,1,2,3. Таким образом,  в частности, множество всех возможных показателей  степени 2 n для любого n состоит из четырех подмножеств:  4k, 4k+ 1, 4k+ 2, 4k+3.

Задание 9-3. Установить последнюю цифру степени y=2 2007

Решение. Имеем 2007=501·4+3, значит f (2007)=f (3)=23=8. Ответ 8.

Требования к знаниям умениям и навыкам

Студенты должны знать определения вычета. Иметь представление о выполнении операций над вычетами. Иметь представление о числовом и цифровом кодировании.