Тема 4. Теория сравнений

Везде далее в этой и следующей теме 5 все a,b,c,… - целые числа; m – натуральное число, m ³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. Если m ₁ – делитель m, то a º b (mod m) Þ a º b (mod m ₁).

2. Сложение: a ₁ º b ₁(mod m), a ₂ º b ₂(mod m) Þ a ₁ + а ₂ º b ₁+ b ₂(mod m).

3. Умножение на k ÎZ:

a º b (mod m) Þ ak º bk (mod mk), тогда в силу свойства 1 ak º bk (mod m).

4. Умножение сравнений:

a ₁ º b ₁(mod m), a ₂ º b ₂(mod m) Þ a ₁ а ₂ º b ₁ b ₂(mod m).

5. Возведение в степень: a º b (mod m) Þ aⁿ º bⁿ (mod m ₁), где n – любое натуральное число.

6. Сокращение сравнений: ak º bk (mod mk) Þ a º b (mod m ₁).

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, то

a ^{j (m)} º 1 (mod m). (11)

Покажем, как можно применить эту теорему для решения некоторых задач.

Пример 7. Найти две последние цифры в десятичной записи чисел 3⁷¹¹, 6⁴²⁷.

Решение.

1) Так как (3,100)=1, то по формуле (11) 3^j(100) º 1(mod 100). Вычислим j(100) по формуле (10): 100=2²5², j(100)=(2²-2) (5²-5)=40, т.е. 3⁴⁰º 1(mod 100). Имеем далее 3⁴º(-19) (mod 100), 3⁸º61(mod 100), 3¹⁰º49(mod 100), 3²⁰º1(mod 100), 3³⁰º49(mod 100), 3³¹º47(mod 100), 3⁷¹¹º 3⁶⁸⁰3³¹º47 (mod 100), а это означает, что последние две цифры десятичной записи числа 3⁷¹¹ – это 4 и 7.

2) Так как (6,100)=2, то формулу (11) при рассмотрении числа 6⁴²⁷ применить нельзя. Мы применим более сложный алгоритм: 6⁴²⁷º6⁴²⁵4×9º4 k (mod 100). По свойству 6 сравнений 6⁴²⁵9º k (mod 25). Теперь (6,25)=1, т.е. 6^j(25)º 1 (mod 25). Вычислим j(25) по формуле (10): 25=5², j(25)=5²-5=20. Итак, 6²⁰º 1 (mod25), 6⁴²⁰º 1 (mod 25); 6²º 11 (mod25), 6³º 16 (mod25), 6⁵ º 1 (mod25), 6⁴²⁵º 1 (mod25), 6⁴²⁵ 9º 9 (mod25). Следовательно, k =9, 4 k =36, последние две цифры десятичной записи числа 6⁴²⁷ – это 3 и 6.

Пример 8. Решить сравнение первой степени 5 х º 3 (mod 17).

Решение. Дадим два способа решения этой задачи.

Способ 1. Так как 3 º 20 (mod 17), то 5 х º 20 (mod 17), по свойству 7 сравнений х º 4 (mod 17), или .

Способ 2. По теореме 2 5^j(17)º 1 (mod 17), или 5¹⁶º 1 (mod 17), если х º 3×5¹⁵ (mod 17), то 5 х º 3 (mod 17), далее действуем как в примере 7. Преимущество этого способа – четкий алгоритм вычислений, недостаток – громоздкость вычислений.

Понятно, что этот пример можно решить простым перебором .