Алгебраическая операция. Коммутативные и ассоциативные операции. Смежные классы по подгруппе. Теорема Лагранжа, страница 6

Докажем теперь обратное утверждение. Пусть  - класс вычетов, являющийся обратимым в . Тогда существует такой класс вычетов  по , что . Выберем в  элемент , в  - элемент . Тогда , т.е.  делится на , или, , . Следовательно, наибольший общий делитель  и  равен 1. А тогда  и  взаимно просты. Теорема доказана.

Обозначим через  множество классов вычетов по , взаимно простых с . Из теоремы 2 следует, что это множество совпадает с множеством обратимых элементов в , а потому, образует группу относительно умножения. Её называют мультипликативной группой обратимых элементов в .

Из того, что множество  образует группу, вытекают следующие утверждения:

1)  Если  и  - классы вычетов по модулю , взаимно простые с , то  - также класс вычетов, взаимно простой с (если , , то ).

2)  Если  - класс вычетов по модулю , взаимно простой с , то существует единственный класс вычетов  по модулю , такой, что . Этот класс вычетов также взаимно прост с . Мы будем называть его обратным к  и обозначать .

3)  Если  - любой класс вычетов по модулю , взаимно простой с ,  - классы вычетов по модулю , взаимно простые с , то .

Из 3) вытекает следующее утверждение:

4)  Пусть группа  состоит из классов вычетов  и пусть . Тогда классы  - это те же классы вычетов , взятые, быть может, в ином порядке.

Докажем это. По свойству 1) все классы вычетов  являются некоторыми из классов вычетов , т.е. принадлежат . При этом если , то по свойству 3) . Так как количество классов вычетов  также равно ,  то множества  и  совпадают.

Утверждения 2) и 4) можно сформулировать на языке приведённой системы вычетов:

2´) Для каждого числа  из приведённой системы вычетов по модулю  найдётся число  из такой же системы вычетов, что .

4´) Если (приведённая система вычетов по модулю ) и  взаимно просто с , то числа  тоже образуют приведённую систему вычетов по модулю .

Решение сравнений первой степени.

Любое сравнение первой степени с неизвестным  можно привести к виду:

                                                   ,                                 (1)

где .

Выясним условия, при которых сравнение (1) имеет:

        а) единственное решение,

        б) несколько решений,

        в) не имеет решений.

Теорема 1. Если , то сравнение (1) имеет единственное решение.

Доказательство. Рассмотрим какую-нибудь полную систему вычетов по модулю :

                                                                                         (2)

По условию, . Тогда  - тоже полная система вычетов по модулю .

Значит, если в (1) подставлять вместо  последовательно все вычеты системы (2), то левая часть (1) пробегает все значения полной системы вычетов. А это означает, что для одного и только для одного  () число  окажется в том же классе, что и , т.е. .

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

Доказательство. По условию, , тогда по теореме Эйлера , откуда , или . Сравнивая последнее сравнение с , находим, что класс  является решением сравнения , согласно теореме 1 – это решение единственное.

Пример. . Так как , то сравнение имеет единственное решение: .

Теперь рассмотрим случай, когда  и  не взаимно просты.

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

Доказательство. Допустим, что сравнение  имеет решение – класс  по модулю , , тогда , или , . Так как , , то и  - противоречие с условием.

Пример. . Так как , а 31 не делится на 5, то решений сравнение  не имеет.

Теорема 4. Если ,  делится на , то сравнение  имеет  различных решений. Все эти решения образуют один класс по модулю .

Доказательство. По условию, , , . Положим , , . Разделим обе части сравнения  и модуль на , получим равносильное сравнение:

                                                                               (3)

В сравнении (3): , поэтому оно имеет единственное решение по модулю : , или ,  - наименьший неотрицательный вычет по модулю ,  - любое целое число, т.е.:

   (4)