Метод преобразования коэффициентов
НОД и Тогда класс вычетов по модулю m является решением сравнения (2.8). По модулю m является решением сравнения (2.9), где функция Эйлера. Теорема 1. Пусть дано сравнение (2.9),. Тогда класс вычетов. Найдем такое целое число, при котором. Например, тогда. Преобразуем произведение. простое число, то. Поэтому. Й способ — метод Эйлера (с помощью функции Эйлера). НОД, поэтому сравнение имеет… Читать ещё >
Метод преобразования коэффициентов (реферат, курсовая, диплом, контрольная)
Теорема1. Пусть дано сравнение:
(2.8).
НОД и Тогда класс вычетов по модулю m является решением сравнения (2.8).
Доказательство. Так как НОД, то сравнение имеет одно решение. Кроме того, Возьмем целое число, тогда, следовательно, получим сравнение, которое является верным сравнением.
Поэтому целое число удовлетворяет сравнению, а, значит, класс вычетов по модулю mявляется решением сравнения. Теорема 1 доказана.
Примеры.
1).
НОД, поэтому сравнение имеет единственное решение.
.
Найдем такое целое число k, чтобы делилось на 5. Например,. Тогда получим:, .
Проверка., 18 делится на 9, поэтому при подстановке в сравнение вместо переменной значения 4, получим верное сравнение, следовательно, число 4 удовлетворяет сравнению, поэтому класс целых чисел, содержащий число 4, является решением сравнения.
Ответ:
2).
НОД, следовательно, сравнение имеет одно решение.
(при будет).
.
Ответ: .
Метод Эйлера
Получим метод решения сравнения.
(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-й способ — метод Эйлера (с помощью функции Эйлера).
Упростим произведение.
решение сравнения.
Ответ:
