Решение сравнений и их приложения

Доказательство.
а) Если (а,p)=1, то согласно теореме Ферма
После умножения обеих частей этого равенства на а, получим:

б) Если (а,p) = 1 , то а делится на p. Но тогда и произведение
а( -1) = а тоже делится на p , то есть а , или .
Итак, для любого целого числа а имеем:

Примеры.
№1.
Найдем остаток от деления 243¹³² на 34.
Решение: 243 5 (mod 34). Тогда 243¹³² 5¹³² (mod 34).
Соглас­но теореме Эйлера 5^φ(34) 1 (mod 34), или 5¹⁶ 1 (mod 34).
Далее делим 132 на 16: 132 = 16 • 8 + 4. Тогда 243¹³² 5¹³² 5^16·8+4 (5¹⁶)· 5⁴ 625
Таким образом, 243¹³² 13 (mod 34).
Следовательно, г= 13.
№2.
Девятая степень однозначного числа n оканчивается цифрой 7; найти это однозначное число.
Решение: так как девятая степень однозначного числа n оканчивается цифрой 7, то остаток от деления числа n⁹ на 10 должен быть равен 7, что равносильно справедливости сравнения n⁹ 7(mod 10)
Так как (7,10)=1, то (n,10)=1. Воспользуемся теоремой Эйлера, получим: n⁴ (mod 10), где φ(10)=4.
Возведём обе части последнего сравнения в квадрат
n⁸ (mod 10).
Тогда n⁹= n⁸·n 1·n (mod 10) и следовательно, n (mod 10).
Ответ: n=7
№3.
Показать, что
Решение: Воспользуемся малой теоремой Ферма: если (а,p)=1, то
.
Числа 1,2,3,4,5,6 взаимно просты с числом 7. На основании указанной теоремы
, (1)
где а= 1,2,3,4,5,6.
Сравнение (1) почленно возведём в куб, получим:
(2)
Складывая почленно сравнения вида (2) имеем при а= 1,2,3,4,5,6:

№4.
Показать, что (
Решение: Каноническое разложение числа 105 = 3·5·7.
Замечая, что (73,3)=(73,5)=(73,7)=1 и 73-простое число, применим малую теорему Ферма к числу 73 по модулям 3,5,7, получим сравнения:



Путём возведения обеих частей сравнений в соответствующие степени, получим сравнения:



Воспользуемся свойством: если некоторое сравнение имеет место по нескольким модулям, то оно справедливо по модулю, являющемуся наименьшим общим кратным данных модулей; следовательно,


,
откуда (

§1. Основные понятия, связанные с решением сравнений.

1. 
   Корни сравнений.
   

Пусть т — целое число и f(х) = а₀х^п + а₁х^п-1 + ... + а_п —многочлен с целыми коэффициентами a₀ ,a_1, …, а_п .Если подста­вить вместо х целые числа, значения многочлена f(х) тоже будут целыми числами.