Теория сравнений (стр. 4 из 12)

Примеры.

1)

. Полная система наименьших неотрицательных вычетов по модулю 7: (так как классы вычетов будут ).

Если

, то , следовательно, не удовлетворяет сравнению.

Если

, то , следовательно, не удовлетворяет сравнению.

Если

, то , следовательно, не удовлетворяет сравнению.

Если

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

Если

, то , следовательно, не удовлетворяет сравнению.

Если

, то , следовательно, не удовлетворяет сравнению.

Если

, то , следовательно, не удовлетворяет сравнению.

Таким образом, сравнение имеет одно решение

или, в другом виде, .

Ответ:

.

2)

.

Классы вычетов по mod 10:

. Полная система наименьших по абсолютной величине вычетов по mod 10: {0, 1, 2, 3, 4, 5, -4, -3, -2, -1}. Проверим для каждого из этих чисел, будет ли выполнено условие . Имеем:

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

Ответ:

.

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

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

(2.4)

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

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

по mod m. Тогда удовлетворяет сравнению, то есть верное сравнение. Отсюда получим, что

(2.5)

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

следует, что

(2.6)

Поэтому из (2.5) и (2.6) получим, что

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

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

Рассмотрим сравнение:

(2.7)

где

, , . Если и то сравнение не имеет решения.

Пусть теперь

, тогда будем иметь:

Поэтому получим:

. Так как по определению НОД число , то из последнего сравнения получим:

Таким образом, полагая в (1), что НОД

, мы пришли к сравнению такого же вида, но с условием: . Исследуем этот случай.

Теорема 1. Пусть дано сравнение (2.7) и НОД

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

Доказательство. Так как НОД

, то класс вычетов по mod m принадлежит мультипликативной группе классов вычетов, взаимно простых с mod m. Поэтому (по свойству группы) уравнение имеет единственное решение , где класс вычетов по mod m, взаимно простых с m. Значит, для , но тогда , отсюда . Обозначим через класс вычетов no mod m, тогда получим, что для следовательно, , a верное сравнение, то есть класс является решением сравнения (2.7). Это решение единственно, так как существует единственный класс . Теорема 1 доказана.