Пример
Найдите минимальное неотрицательное трехзначное число, которое сравнимо с выражением 9*156+8*155+9*154+7*153+9*152+2*15+1 по модулю 14.
Итак, для начала давайте обратимся к сумме сравнений
a≡b(mod m), c≡d(mod m) => a+c≡b+d(mod m)
и скажем, что если выражение представляет из себя сумму значений, то мы можем каждое слагаемое заменять на сравнимое с ним значение. Т.е. если у нас изначально было a+c, и мы знаем, что a≡b(mod m), c≡d(mod m), то мы пользуемся вот таким переходом a+c≡b+d(mod m).
Теперь посмотрим на первое слагаемое 9*156, и попытаемся его заменить на наименьшее неотрицательное сравнимое с ним. С произведением мы можем проделать тот же набор операций, что и с суммой выше, и тогда нам нужно будет отдельно рассмотреть 9 и 156.
Довольно очевидно, что для 9 наименьшее неотрицательное с которым оно сравнимо – оно само. 9≡9(mod 14).
Для 156 воспользуемся свойством степеней a≡b(mod m) <=> at≡bt(mod m) 156≡15(mod 14), ну а от 15 довольно легко найти остаток от деления на 14. 15≡1(mod 14).
Итого 9*156≡9*1(mod 14) <=> 9*1≡9(mod 14).
Аналогичные действия проделаем со всеми слагаемыми.
8*155≡8(mod 14).
9*154≡9(mod 14).
7*153≡7(mod 14).
9*152≡9(mod 14).
2*15≡2(mod 14).
Итого, 9*156+8*155+9*154+7*153+9*152+2*15+1≡9+8+9+7+9+2+1(mod 14).
9+8+9+7+9+2+1≡45(mod 14)
45≡3(mod 14).
И т.к. минимальное целое неотрицательное число, с которым сравнимо исходное выражение равно 3, то в целом исходное выражение сравнимо с любым выражением вида 14n+3, где n – целое число. А значит наша задача решить неравенство 100≤14n+3≤999.
100≤14n+3≤999;
97≤14n≤996.
6(13/14) ≤n≤71(2/14).
Минимальное n, которое нам подходит – это 7. 14*7+3=101.
Ответ: 101.