Изложение теоретического материала иллюстрируется большим количеством примеров с подробными решениями
 Скачать 1.34 Mb.
|
2.3 Теорема о разрешимости сравненияРассмотрим сравнение:
где , , . Если и то сравнение не имеет решения. Пусть теперь , тогда будем иметь: Поэтому получим: . Так как по определению НОД число , то из последнего сравнения получим: Таким образом, полагая в (1), что НОД , мы пришли к сравнению такого же вида, но с условием: . Исследуем этот случай. Теорема 1. Пусть дано сравнение (2.7) и НОД . Тогда сравнение (2.7) имеет единственное решение. Доказательство. Так как НОД , то класс вычетов по mod m принадлежит мультипликативной группе классов вычетов, взаимно простых с mod m. Поэтому (по свойству группы) уравнение имеет единственное решение , где класс вычетов по mod m, взаимно простых с m. Значит, для , но тогда , отсюда . Обозначим через класс вычетов no mod m, тогда получим, что для следовательно, , a верное сравнение, то есть класс является решением сравнения (2.7). Это решение единственно, так как существует единственный класс . Теорема 1 доказана. Пример 1. НОД (5,9) = 1, следовательно, сравнение имеет одно решение. Найдем его способом «подбора», то есть перебирая все числа из полной системы вычетов по modm: {0, 1, 2, 3, 4, 5, б, 7, 8} (m = 9). следовательно, удовлетворяет сравнению, поэтому решением будет класс вычетов по modm или, по-другому, . А так как данное сравнение имеет 1 решение, то остальные числа : 5, 6, 7, 8 проверять уже не надо. Ответ: . Заметим, что для нахождения решения сравнения первой степени с одной переменной (если оно есть) существует несколько способов: 1) подбора; 2) преобразования коэффициентов; 3) Эйлера (с помощью функции Эйлера); 4) цепных дробей. Если модуль m является простым числом, то есть , число не делится на , то сравнение имеет единственное решение. Следовательно, множество классов вычетов образует поле по отношению сложения и умножения классов вычетов. Его обозначают через Пример 2. Вычислить остаток при делении на 15. Решение. 1 способ. Сравнение для применения теоремы Эйлера сократим на 3 (очевидно, . Так как , то по теореме Ферма показатель 99 можно уменьшить по модулю 4. Получаем, что из следует: . Умножаем на 3 обе части сравнения и модуль: , т.е. . Аналогично вычисляем . Отсюда почленным сложением сравнений найдем: . Затем, возводя в 100-ю степень обе части сравнения, получаем . Ответ: 1. 2 способ. Сравнение рассмотрим отдельно по модулям 3 и 5 (делители 15). Так как и , то , . Среди целых чисел от 0 до 14 (возможные остатки при делении на 15) только 1, 6, 11 сравнимы с 1 по модулю 5. А среди этих трех только 1 сравнима с 1 по модулю 3, т.е. . Тогда . 3 способ. Число не делится на 3 (первое слагаемое делится, а второе не делится) и не делится на 5. Так как 3 и 5 есть простые числа, то с ними взаимно просто и взаимно просто с 15. По теореме Эйлера , Ответ: 1. Пример 3. Разложить в цепную дробь. Проверить разложение, свернув цепную дробь последовательным вычислением подходящих дробей. Решение. Найдём элементы цепной дроби как частные в алгоритме Евклида: Сделаем сокращённую запись: Пусть обозначает элемент цепной дроби, ю подходящую дробь, подходящей дроби. Будем вычислять подходящие дроби по рекуррентной формуле , используя схему:
Как видно, последняя подходящая дробь совпадает с исходным числом. Замечание. Непосредственное сворачивание конечной цепной дроби «снизу вверх» обычно громоздко: Задачи для самостоятельного решения. Задача 1. Сократите дробь , применяя алгоритм Евклида. Задача 2. Сколько натуральных чисел взаимно просто с 520 и не превосходит это число? (решить с помощью функции Эйлера) Задача 3. Решить сравнение Задача 4. Найти все целочисленные решения уравнения |