4.6 ОТНОШЕНИЕ СРАВНИМОСТИ

Модулярная арифметика — это один из главных инструментов, которыми располагает теория чисел. Мы мельком коснулись ее в гл. 3, когда имели дело с бинарной операцией — как правило, в качестве одной из операций наряду с другими в составе некоторого выражения. В этой главе будет использоваться и в качестве самостоятельного выражения, в связи с чем будет более удобна несколько иная форма ее записи:

К примеру, так как . Формула может быть прочитана как сравнимо с по модулю Данное понятие имеет смысл и тогда, когда — произвольные вещественные числа, но мы почти всегда будем использовать его только для целых чисел.

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

Действительно, если то определение операции из (3.21) указывает, что при некоторых целых И наоборот, если то при в противном случае

Зачастую проще применять характеризацию нежели из (4.35). Так, ибо кратно 5 — не нужно вычислять ни ни

Знак сравнения очень напоминает знак ибо сравнения весьма схожи с равенствами. Например, сравнение является отношением эквивалентности, т. е. оно обладает свойствами рефлексивности симметричности и транзитивности Все эти свойства легко доказуемы, поскольку всякое отношение которое удовлетворяет соотношению для некоторой функции является отношением эквивалентности. (В нашем случае Кроме того, сравнимые элементы можно складывать и вычитать без потери сравнимости:

Действительно, если кратны то это же верно для и для Кстати, вовсе не обязательно писать после каждого знака если величина модуля не меняется, то

достаточно упомянуть его лишь один раз без изменения последующего смысла. В этом состоит большое удобство понятия сравнения.

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

Доказательство: . А повторное применение этого свойства умножения делает его справедливым и для степеней:

К примеру, поскольку то это означает, что кратно 3 тогда и только тогда, когда четно.

Таким образом, большую часть алгебраических операций, которые обыкновенно выполняются с равенствами, можно выполнять и со сравнениями. Большую — но не все: операция деления блистательно отсутствует. Если то это не всегда означает, что . К примеру, но

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

К примеру, из того, что вполне закономерен вывод, что если только модуль не кратен 5.

Для доказательства этого свойства снова воспользуемся расширением правила (4.5) для находя такие, что Тогда, если то можно умножить обе части сравнения на получая . А поскольку то следовательно, Это доказательство показывает, что при рассмотрении сравнений по модулю число ведет себя наподобие числа в силу чего его называют „обратным d по модулю

Другое применение операции деления к сравнениями — деление модуля наряду с другими числами:

Это правило справедливо для всех вещественных чисел поскольку оно основывается только на распределительном законе имеем Так, например, из того, что заключаем, что

Теперь можно объединить (4.37) и (4.38) и получить общее правило, изменяющее величину модуля в наименьшей возможной степени:

Действительно, можно умножить на где получая сравнение которое можно разделить на

Немного разовьем подобную идею изменения величины модуля. Если нам известно, что то а должно быть сравнимо с по модулю 10, а также по модулю любого другого делителя 100. Сказать, что кратно 100 — это сильнее, чем сказать, что кратно 10. В общем случае

поскольку величина, кратная кратна и

Обратно, если известно, что по некоторым двум малым модулям, можно ли сделать вывод, что и по какому-либо большему модулю? Можно — соответствующее правило гласит, что

Так, если известно, что по модулю 12 и 18, то можно с уверенностью заключить, что Основанием для этого служит то, что если разность кратна как так и то она кратна и Это вытекает из принципа единственности разложения на простые множители.

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

К примеру, тогда и только тогда, когда Говоря по-другому, если известны то этого вполне достаточно для установления Это частный случай китайской теоремы об остатках (см. упр. 30), открытой Сунь Цзы из Китая около 350 г. н. э.

Модули в (4.42) могут быть далее разложены на взаимно простые множители, пока не будут выделены все различные простые числа. Следовательно,

если разложение (4.11) числа на простые множители имеет вид Сравнения по модулю степеней простых чисел — это те „кирпичики" из которых строятся все сравнения по модулю целых чисел.