Везде далее в этой и следующей теме 5 все a,b,c,… - целые числа; m – натуральное число, m³2; р,р1,р2,… - простые числа; (а,b) обозначает НОД (наибольший общий делитель) целых чисел a и b; если (а,b)=1, то числа a и b называются взаимно простыми.
Определение 3. Числа a и b называются сравнимыми по модулю m: a º b(mod m), если a – b без остатка делится на m.
Это определение равносильно тому, что числа a и b имеют одинаковые остатки при делении на m. Отношение сравнимости является отношением эквивалентности, т.к. легко проверяются: рефлексивность: a º a (mod m),
симметричность: a º b(mod m) Þ b º a (mod m) и
транзитивность: a º b(mod m) Þ b º с (mod m) Þ a º с(mod m).
Приведем еще ряд свойств сравнений.
1. Если m1 – делитель m, то a º b(mod m) Þ a º b(mod m1).
2. Сложение: a1 º b1(mod m), a2 º b2(mod m) Þ a1 +а2 º b1+b2(mod m).
3. Умножение на kÎZ:
a º b(mod m) Þ ak º bk (mod mk), тогда в силу свойства 1 ak º bk (mod m).
4. Умножение сравнений:
a1 º b1(mod m), a2 º b2(mod m) Þ a1а2 º b1b2(mod m).
5. Возведение в степень: a º b(mod m) Þ an º bn(mod m1), где n – любое натуральное число.
6. Сокращение сравнений: ak º bk (mod mk) Þ a º b(mod m1).
7. Сокращение на взаимно простое с m число: если (с,m)=1, то aс º bс (mod m)Û a º b(mod m).
Так как отношение сравнения является отношением эквивалентности на множестве целых чисел, то Z разбивается на классы эквивалентности, называемые вычетами: , где мы выписали все возможные остатки от деления целых чисел на m.
Обозначим через j(m) – число всех натуральных чисел из множества {1,…,m-1}, взаимно простых с m. Функция j(m) называется функцией Эйлера. Если - разложение в произведение простых, то
j(m)= … . (10)
Роль функции Эйлера в теории сравнений определяется следующей теоремой, доказанной Эйлером.
Теорема 2. Если (а,m)=1, то
aj(m)º 1 (mod m). (11)
Покажем, как можно применить эту теорему для решения некоторых задач.
Пример 7.Найти две последние цифры в десятичной записи чисел 3711, 6427.
Решение.
1) Так как (3,100)=1, то по формуле (11) 3j(100) º 1(mod 100). Вычислим j(100) по формуле (10): 100=2252, j(100)=(22-2) (52-5)=40, т.е. 340º 1(mod 100). Имеем далее 34º(-19) (mod 100), 38º61(mod 100), 310º49(mod 100), 320º1(mod 100), 330º49(mod 100), 331º47(mod 100), 3711º 3680331º47 (mod 100), а это означает, что последние две цифры десятичной записи числа 3711 – это 4 и 7.
2) Так как (6,100)=2, то формулу (11) при рассмотрении числа 6427 применить нельзя. Мы применим более сложный алгоритм: 6427º64254×9º4k (mod 100). По свойству 6 сравнений 64259ºk (mod 25). Теперь (6,25)=1, т.е. 6j(25)º 1 (mod 25). Вычислим j(25) по формуле (10): 25=52, j(25)=52-5=20. Итак, 620º 1 (mod25), 6420º 1 (mod 25); 62º 11 (mod25), 63º 16 (mod25), 65 º 1 (mod25), 6425º 1 (mod25), 6425 9º 9 (mod25). Следовательно, k=9, 4k=36, последние две цифры десятичной записи числа 6427 – это 3 и 6.
Пример 8. Решить сравнение первой степени 5х º 3 (mod 17).
Решение. Дадим два способа решения этой задачи.
Способ 1. Так как 3 º 20 (mod 17), то 5х º 20 (mod 17), по свойству 7 сравнений х º 4 (mod 17), или .
Способ 2. По теореме 2 5j(17)º 1 (mod 17), или 516º 1 (mod 17), если х º 3×515 (mod 17), то 5х º 3 (mod 17), далее действуем как в примере 7. Преимущество этого способа – четкий алгоритм вычислений, недостаток – громоздкость вычислений.
Понятно, что этот пример можно решить простым перебором .