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

Получили, что ни одно из чисел, взятых из полной системы вычетов, не удовлетворяет сравнению, следовательно, данное сравнение не имеет решения.

Ответ: .

2.2 Теорема о неразрешимости сравнения

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

, . Тогда сравнение (2.4) не имеет решения.

Доказательство. От противного. Предположим, что существует решение: класс вычетов по mod m. Тогда удовлетворяет сравнению, то есть верное сравнение. Отсюда получим, что

Из условия теоремы: следует, что

Поэтому из (2.5) и (2.6) получим, что и , отсюда следует, что . Получили противоречие:так как сделали неправильное предположение. Отбросив его, получим, что сравнение (2.4) не имеет решения. Теорема 1 доказана.

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

следовательно, удовлетворяет сравнению, поэтому решением будет класс вычетов по mod m или, по-другому, .

А так как данное сравнение имеет 1 решение, то остальные числа : 5, 6, 7, 8 проверять уже не надо.

Ответ: .

Заметим, что для нахождения решения сравнения первой степени с одной переменной (если оно есть) существует несколько способов:

1) подбора;

2) преобразования коэффициентов;

3) Эйлера (с помощью функции Эйлера);

4) цепных дробей.

Если модуль m является простым числом, то есть , число не делится на , то сравнение имеет единственное решение. Следовательно, множество классов вычетов образует поле по отношению сложения и умножения классов вычетов. Его обозначают через

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