Сборник задач по курсу «Логическое программирование»: Учебное пособие, страница 19

Рис. 2. Пример графа и его матрицы инцидентности

Модульная арифметика (арифметика вычетов)

Если оперировать только с целыми числами и приводить результаты по модулю M, то такая арифметическая система называется одномодульной арифметикой вычетов. Целое число M > 1 при этом называется модулем арифметической системы. Для трех основных арифметических операций в этой арифметике (сложения, умножения и вычитания) можно записать простые утверждения:

ü  X есть сумма чисел A и B в арифметике вычетов по модулю M, если X = (A + B) mod M;

ü  X есть произведение чисел A и B в арифметике вычетов по модулю M, если X = (A * B) mod M;

ü  X есть разность чисел A и B в арифметике вычетов по модулю M, если X = (A + M – B mod M) mod M.

Для осуществления деления в арифметике вычетов приходится прибегать к более громодкой процедуре. В обычной арифметике можно записать такое равенство A/B = A*B^-1. Таким образом, для того чтобы поделить A на B, достаточно умножить A на обратное к B число. В арифметике вычетов именно так и поступают. X есть результат деления числа A на число B в арифметике вычетов по модулю M, если X = (A * B^-1mod M) mod M. Для расчета обратного элемента (числа) к B по модулю M, т.е. B^-1mod M, используется расширенный алгоритм Евклида. При произвольных значениях модуля для некоторых чисел обратный элемент может и не существовать. Если в качестве модуля арифметики брать простое целое число, то для любого числа в такой арифметике существует обратный элемент.

Расширенный алгоритм Евклида (как и обычный) предназначен для нахождения наибольшего общего делителя двух целых чисел a,b – НОД(a,b) = d. Однако, кроме решения этой «основной задачи» он позволяет находить целые числа x,y, являющиеся решениями уравнения ax + by = d. Псевдокод для этого алгоритма выглядит так.