 |
Методическое указание к выполнению лабораторной работы
|
|
|
|
Лабораторная работа № 4
Модульная арифметика: основы вычисления в классах вычетов
Цель работы
- Ознакомиться с использованием классов вычетов в библиотеке “FLINT\C”.
- Научиться выполнять арифметические операции с классами вычетов с использованиембиблиотеки“FLINT\C”.
Методическое указание к выполнению лабораторной работы
При делении целого числа а на натуральное число m, существует единственное представление
где q - целая часть числа
r - остаток от деления
Число m делит (a – r) без остатка
Это соотношение Гаусс предложил записывать как
a ≡ r mod m
читается оно как “ a сравнимо c r по модулю m ”;
число r называется “ вычетом по модулю m ”
Существуют определения сравнимых чисел
Определение 1. Целые числа а и r называются сравнимыми по модулю m, если их разность делится без остатка на m.
Определение 2. Целые числа а и r называются сравнимыми по модулю m, если их остатки при делении на m одинаковы.
Все числа, сравнимые с числом r по модулю m, одинаково ведут себя при делении на m — они дают остаток r.
Объединение таких чисел в одно множество, называемое классом вычетов по модулю m, обозначается как 
( чтобы отличить его от числа a).
Значит, - не число, а бесконечная совокупность чисел.
Все множество Z целых чисел распадается на m классов вычетов по модулю m.
Так, например:
Класс вычетов 
по модулю 5 будет включать в себя все числа
= (-10,-5, 0, 5,10, 15,……)
класс вычетов 
по модулю 5 будет включать в себя все числа
={-9, -4, 1, 6,11, 16,…......}
класс вычетов 
по модулю 5 будет включать в себя все числа
= {-8, -3, 2, 7, 12, 17, ….}
класс вычетов 
по модулю 5 будет включать в себя все числа
|
|
|
= {-7, -2, 3, 8, 13, 18 …. }
а класс вычетов 
по модулю 5 будет включать в себя все числа
={-6,-1, 4, 9, 14, 19,……..} и т.д.
Множества чисел в классах вычетах не пересекаются, а все множество целых чисел Z можно представить как множество классов вычетов по модулю 5
Z= 
Над классами вычетов по одному и тому же модулю можно проводить арифметические операции – сложение, вычитание и умножение. Результатом всех этих операций будет новый класс вычетов.
Принцип вычислений в модульной арифметике заключается в следующем: к операндам применяется соответствующая обычная («немодульная») операция, а затем результат делится с остатком на модуль.
Операция сложения определяется следующим образом:
· в каждом из слагаемых классов вычетов берут по представителю, давших названия слагаемым класса и складывают их;
· находят вычет по модулю(остаток от деления на модуль) от полученной суммы.
Этот вычет и называют суммой данных классов вычетов.
Например, сложим классы вычетов 4 и 5 по модулю 6. Для этого возьмем сами остатки 4 и 5, давшие названия слагаемым классам.
· Их сумма равна 9.
- Вычет по модулю 6(остаток от деления 9/6) равен 3.
Результат 4+5=3.
Пример 2. Сложим классы вычетов 0 и 1 по модулю 2.
· Сумма их представителей равна 1.
- Вычет по модулю 2 (остаток от деления 1/2) равен 1.
Операции вычитания и умножения выполняются аналогично операции сложения
Вычтем из класса вычетов 1 и классы вычетов 2 по модулю5.
· Разность их представителей равна- 1.
- Вычет по модулю 5 (остаток от деления 1/5) равен 1.
Умножим класс вычетов 2 на класс вычетов 4 по модулю5.
· Произведение их представителей равно 8.
- Вычет по модулю 5 (остаток от деления 8/5) равен 3.
Деление классов вычетов
Разделить класс вычетов a на класс вычетов b — значит найти такой класс вычетов х, что ах=b. Для целых чисел задача деления разрешима не всегда, но уж если она выполняется, то единственным образом. Это связано с тем, что произведение двух целых чисел равно нулю лишь в случае, когда хоть один из множителей равен нулю. Но в Fm дело обстоит не так. Взглянув на таблицу умножения для f«, замечаем, что нули стоят в ней не только в первой строке и первом столбце (там, где один из множителей равен нулю).
|
|
|
Нулю равны и произведения 2 • 3, 3 • 4, хотя множители отличны от нуля. Как говорят, в F есть делители нуля (класс вычетов а называется делителем нуля, если он отличен от 0, но существует такой класс b, что а - b =0. Делителями нуля оказались классы 2, 3. 4. Числа 2, 3, 4 имеют общее свойство — они не являются взаимно простыми с модулем 6. Это наводит на мысль о справедливости следующей теоремы:
Теорема 2. Класс вычетов а в Fm не является делителем нуля в том и только в том случае, когда а и т взаимно просты.
В случае, когда модуль является простым числом, можно делить на любой ненулевой класс вычетов — в этом случае все такие классы взаимно просты с модулем!
|
|
|
