Разнообразные задачи можно решать с помощью метода контроля, основанного на свойствах сравнений. Развитые на этой основе методы контроля арифметических и логических операций называют контролем по модулю.
Рассмотрим основные положения из теории сравнений.
Если целым числам А и В соответствует один и тот же остаток от деления на третье число р, то числа А и В равноостаточны друг другу по модулю р или сравнимы по модулю р. Сравнения — уравнения типа:
А = В(mod р).
Сравнимость двух чисел равносильна возможности представить их в алгебраическом виде
А = В + р1.
Сравнения обладают рядом свойств:
Сравнения можно почленно складывать. Если А1 ≡ В1(mod р);
А2 ≡ В2(mod р);...; Аn≡Вп(mod р), то А1 + А2 + ... + Ап ≡ В1 + В2 + ... + Вn(mod р).
Следовательно, слагаемое, стоящее в какой-либо части сравнения, можно переносить в другую часть, поменяв при этом его знак, т. е. А + В ≡ С(mod р) или А ≡ С - В(mod р).
Два числа, сравнимые с третьим числом, сравнимы и между собой:
если А ≡ В(mod р); С = B(mod р), то А ≡ С(mod р).
Сравнения можно почленно перемножить. Пусть A1 ≡ В1 (mod p);
А2 ≡ В2(mod p). Тогда A1 = B1 + l1p; А2 = В2 + l2р.
После умножения получаем А1А2 = В1В2 + В1l2p + В2l1р + l1l2pp. Следовательно, А1А2 = В1В2 + Np, или в общем случае:
А1А2А3...Аm ≡ В1В2В3...Вm (mod p).
Из свойства 3 также следует, что обе части сравнения можно умножить на одно и то же целое число.
Пусть А ≡ В(mod p); К = К(mod p). Тогда АК ≡ ВК(mod p).
Обе части сравнения и модуль можно умножить на одно и то же число:
А = В + lp; Аm = Вm + mlp, т. е. Аm = Вm(mod mp).
Обе части сравнения и модуль можно разделить на любой общий делитель. Пусть А ≡ B(mod p), где А = ad, В = bd, Р = p1d. Тогда А = В + lp.
Подставив в это выражение значения А, В и Р, получим
ad = bd + lp1d.
Разделив уравнение на d, получим а = b + lp1, т. е. a = b(mod p1).
Обе части сравнения можно возвести в степень. Если А ≡ В(mod p),
то А" = В"(mod p).
Из свойства 6 следует, что над сравнениями можно провести операцию извлечения корня n-й степени.
Рассмотренные выше свойства сравнений используются для осуществления операции контроля.
Существуют два метода получения контрольного кода: числовой и цифровой.