Теория сравнений

Пример 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. Найти все целочисленные решения уравнения

2.4 Метод преобразования коэффициентов

Теорема1. Пусть дано сравнение:

НОДи Тогда класс вычетов по модулю m является решением сравнения (2.8).

Доказательство. Так как НОД, то сравнение имеет одно решение. Кроме того, Возьмем целое число , , тогда , следовательно, получим сравнение: , которое является верным сравнением.

Поэтому целое число удовлетворяет сравнению, а, значит, класс вычетов по модулю m является решением сравнения. Теорема 1 доказана.

Примеры.

1)

НОД, поэтому сравнение имеет единственное решение.

.

 Скачать реферат