Свойства сравнимости

1. Два числа, сравнимые с третьим по одному модулю, сравни­мы между собой:

2. Сравнения можно складывать и вычитать:

(а º b(mod p); cº d(mod p)) => (а ± с) º (b ± d)(mod p).

Слагаемые можно переносить из одной части сравне­ния в другую с противоположным знаком.

3. Сравнения можно перемножать:

(a º b(mod p), с º d(mod p)) => (ас º bd(mod p)).

4. Обе части сравнения можно умножить на одно и то же целое число k:

(а º 6(mod p}) => (ak º bk(mod p)).

5. Обе части сравнения и модуль можно умножить на одно и то же число:

(а º b (mod p)) => (akº bk(mod pk)).

6. Обе части сравнения можно возвести в степень (следствие свойства 3):

(а º b (mod p)) => (аⁿ = bⁿ (mod p)).

Понятие сравнения ввел К.Ф.Гаусс в работе " Ариф­метические исследования" (1802). Алгебра вычетов возникает в тех случаях, когда рассматриваются некоторые циклически повторя­ющиеся события, например время в течение дня, повторяющееся каждые 24 часа, углы по окружности, повторяющиеся через пе­риод 2к, и т.д.

Алгебра вычетов - один из тех разделов математики, которые рождались как некоторые формальные рассуждения и только спустя годы нашли свое практи­ческое применение.

Пример. Для степени y=2ⁿ (n–натуральное число) установить классы сравнимости. Установить зависимость последней цифры этой степени от ее показателя.

Решение и комментарии.

Как известно, натуральные степени числа 2 оканчиваются циф­рами {2, 4, 8, 6}. См. таблицу нескольких степеней числа 2.

Опреде­лим функцию, которая ставит в соответствие каждому натуральному числу п последнюю цифру числа 2^я:

n	2n	Последняя цифра 2т

f: N®{2, 4, 8, 6},

Эта функция f(n) периодична с периодом 4. Это значит, что для целого числа k: f(n)=f(n+4)= f(n+4k),.

Причем справедливы так же равенства: f(n)=f(n-4)= f(n-4k)

Последнее равенство означают, что для любого п нужно найти минимальное натуральное т, такое, что f(m) = f(m + 4k) = f(n).

Но это задача на делении с остатком числа n на 4:

n=4k+m, k-частное, т - остаток.

Очевидно, последняя цифра числа 2" зависит от остатка, полученного при делении показателя n степени 2 ⁿ на 4.

Отразим этот факт в записи функции: f(n)= f(n mod 4)

Из этой формулы можно установить, если f(n mod 4)=0, то

При делении чисел на 4 " nÎ N, останки могут быть: 0, 1, 2, 3. Таким образом, в частности, множество всех возможных показателей степени 2 ⁿ для любого n состоит из четырех подмножеств: 4k, 4k+ 1, 4k+ 2, 4k+3.

Пример. Установить последнюю цифру степени y=2 ²⁰⁰⁷

Решение. Имеем 2007=501·4+3, значит f (2007)=f (3)=2³=8. Ответ