Сравнения первой степени.

Найдем условия разрешимости сравнения первой степени.

ТЕОРЕМА 4.1. Если , то сравнение

имеет одно и только одно решение.

Доказательство. По условию, число а — взаимно простое с . Согласно теореме 3.5, существует целое число а, обратное к а по модулю , т. е.

Умножив обе части (1) на а, получим

Следовательно, сравнение (1) имеет не больше одного решения. С другой стороны, (2) есть решение сравнения (1), так как

Таким образом, класс вычетов является единственным решением сравнения (1).

ТЕОРЕМА 4.2. Пусть . Сравнение

разрешимо тогда и только тогда, когда . Если то сравнение (1) имеет своими решениями точно d классов вычетов по модулю , которые составляют один класс вычетов по модулю .

Доказательство. Пусть Если сравнение (1) имеет решение , то , где k — целое число. Так как , то отсюда следует, что d делит b.

Предположим теперь, что b делится на d, и докажем, что сравнение (1) имеет d решений. Пусть . Сравнение (1) равносильно сравнению

Согласно теореме 4.1, сравнение (2) имеет единственное решение где — число, обратное по модулю Пусть Класс вычетов распадается на следующие d классов вычетов по модулю :

Легко видеть, что классы вычетов (3) являются различными по модулю . Таким образом, сравнение (2) имеет своими решениями классы вычетов (3), т. е. точно d классов вычетов по модулю , которые составляют один класс вычетов по модулю

Отметим, что совокупность решений (3) сравнения (1) есть смежный класс аддитивной группы 3 классов вычетов по модулю по подгруппе

Обратно: любой смежный класс группы по подгруппе можно задать как множество решений некоторого линейного сравнения по модулю .