Пример 1.

НОД (5,9) = 1, следовательно, сравнение имеет одно решение. Найдем его способом «подбора», то есть перебирая все числа из полной системы вычетов по
mod m: {0, 1, 2, 3, 4, 5, б, 7, 8} (
m = 9).

следовательно,

удовлетворяет сравнению, поэтому решением будет класс вычетов

по
mod m или, по-другому,

.
А так как данное сравнение имеет 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. Найти все целочисленные решения уравнения
Теорема 1. Пусть дано сравнение:
НОД

и

Тогда класс вычетов

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

, то сравнение

имеет одно решение. Кроме того,

Возьмем целое число

,

, тогда

, следовательно, получим сравнение:

, которое является верным сравнением.
Поэтому целое число

удовлетворяет сравнению, а, значит, класс вычетов

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

НОД

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

.
Найдем такое целое число k, чтобы

делилось на 5. Например,

. Тогда получим:

,

.