Теория сравнений (стр. 6 из 12)
Проверка.
, 18 делится на 9, поэтому при подстановке в сравнение вместо переменной значения 4, получим верное сравнение, следовательно, число 4 удовлетворяет сравнению, поэтому класс целых чисел, содержащий число 4, является решением сравнения.Ответ:
2)
НОД
, следовательно, сравнение имеет одно решение. 
(при 
будет 
) 
, 
Ответ:
.2.6 Метод Эйлера
Получим метод решения сравнения
 | (2.9) |
с помощью функции Эйлера.
Теорема 1. Пусть дано сравнение (2.9),
. Тогда класс вычетов 
по модулю m является решением сравнения (2.9), где
функция Эйлера.Доказательство. Так как
, то по теореме Эйлера имеет место сравнение 
где 
функция ЭйлераВыберем
, тогда при подстановке его вместо 
в сравнение (2.9) и, учитывая, что 
получим сравнение
которое является верным в силу теоремы Эйлера. Следовательно,
удовлетворяет сравнению (2.9), а класс вычетов 
по модулю m является решением сравнения, или, по-другому,
решение сравнения (2.9). Теорема 1 доказана.Примеры.
1)
, следовательно, сравнение имеет одно решение, 
Преобразуем произведение
. 
простое число, то 
. Поэтому 
, 
Ответ:
.2)
. 
, поэтому сравнение имеет одно решение.1-й способ – способ подбора. Полная система наименьших по абсолютной величине вычетов по модулю 34: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 25, 26, 27, 28, 29, 30, 31, 32, 33}.
Проверим, какое из этих чисел
удовлетворяет сравнению, то есть 
. Это будет 
, так как 
. Следовательно, 
решение сравнения.Ответ:
.2-й способ – способ преобразования коэффициентов.
, k 
Найдем такое целое число
, при котором 
. Например, 
, тогда 
. 
, 
решение сравнения.Ответ:
3-й способ – метод Эйлера (с помощью функции Эйлера).
Упростим произведение
решение сравнения.Ответ:
3. Сравнения высших степеней
3.1 Основные понятия
Определение 1. Сравнением n-й степени с одной переменной называется сравнение вида
 | (3.1) |
где
многочлен с целыми коэффициентами:  | (3.2) |
причем,
.Целое число
удовлетворяет сравнению (3.1), если сравнение 
является верным сравнением.Теорема 1. Пусть дано сравнение (3.1) и целое число
удовлетворяет сравнению (3.1). Тогда весь класс 
по mod m состоит из чисел, удовлетворяющих сравнению (3.1).Доказательство. Число
удовлетворяет сравнению (3.1), следовательно, 
верное сравнение. Для любого 
всегда 
. Но тогда по свойству сравнений 
, поэтому по транзитивности получим, что 
, отсюда следует, что число 
удовлетворяет сравнению (3.1). А так как 
произвольное из 
, то, следовательно, весь класс вычетов по mod m состоит из чисел, удовлетворяющих сравнению (3.1). Теорема 1 доказана.Определение 2. Решением сравнения (3.1) называется класс вычетов по модулю m, состоящий из чисел, удовлетворяющих сравнению (3.1).
Если класс
mod m является решением сравнения (3.1), то будем говорить, что класс удовлетворяет сравнению (3.1). Числом решений сравнения (3.1) называется число классов вычетов по mod m, удовлетворяющих сравнению (3.1).Задача нахождения чисел, удовлетворяющих сравнению (3.1), сводится к нахождению классов, удовлетворяющих уравнению
