Сравнения

Если при делении на целое положительное число т два числа а и b дают один и тот же остаток, то они называются равноостаточными или сравнимыми по модулю т. Записывается это так:

Свойства сравнения:

1) (рефлексивность);

2) если то (симметричность);

3) если то (транзитивность).

Теорема. тогда и только тогда, когда существует целое число t, для которого

Доказательство необходимости. Пусть , тогда откуда

Обозначив через t и получим представление а в виде

Доказательство достаточности. Пусть и Тогда т.е. число а дает тот же остаток при делении на т, что и число b. Теорема доказана. ■

Теорема. тогда и только тогда, когда a-b делится на т.

Доказательство проводится аналогично. ■

Свойства сравнений, подобные свойствам равенств:

1) Если то т.е. сравнения можно почленно складывать.

Доказательство: По условию тогда а это значит, что

2) Если то т.е. сравнения можно почленно перемножать.

Доказательство: следовательно, т.е.

3) Если , то для любого целого числа k.

Доказательство: . Отсюда

4) Если , то .

Доказательство: По условию делится на т; k и т взаимно просты. Из теоремы Евклида следует, что a-b делится на т, а это равносильно тому, что .

Пример: Установить признак делимости на 11.

Решение: Представим число N в виде , где . Так как . То . Отсюда, N делится на 11 тогда и только тогда. Когда на 11 делится