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

Сравнение первой степени перенесением свободного члена (с обратным знаком) в правую часть можно привести к виду

ах º b(mod m). (1)

Приступая к исследованию вопроса о числе решений, мы сначала ограничим сравнение условием (а, m) = 1.

Наше сравнение имеет столько решений, сколько вычетов полной системы ему удовлетворяет. Но когда x пробегает полную систему вычетов по модулю m, то ах пробегает полную систему вычетов (глава 3, п. 4, Теорема 2). Следовательно, при одном и только одном значении x, взятом из полной системы, ах будет сравнимо с b. Итак, при (а, m) = 1 сравнение (1) имеет одно решение.

Пусть теперь (a, m) = d > l. Тогда, чтобы сравнение (1) имело решения, необходимо (глава 3, п. 3, Свойство 5), чтобы b делилось на d, иначе сравнение (1) невозможно ни при каком целом х. Предполагая поэтому b кратным d, положим а = a₁d, b = b_ld, m = m₁d. Тогда сравнение (1) будет равносильно такому (по сокращении на d): a₁xºb₁(mod m₁), в котором уже (a₁, m₁) = l, и потому оно будет иметь одно решение по модулю m₁. Пусть х₁ - наименьший неотрицательный вычет этого решения по модулю m_l, тогда все числа х, образующие это решение, найдутся в виде

x º x₁(mod m₁). (2)

По модулю же m числа (2) образуют не одно решение, а больше, именно столько решений, сколько чисел (2) найдется в ряде 0, 1, 2, ,.., m - 1 наименьших неотрицательных вычетов по модулю m. Но сюда попадут следующие числа (2):

x_l, x₁ + m₁, х₁ + 2m₁, …, x_l + (d - 1)m_l,

т. е. всего d чисел (2); следовательно, сравнение (1) имеет d решений.

Собирая все доказанное, получаем теорему:

Теорема 1: Пусть (a, m) = d. Сравнение аx º b(mod m) невозможно, если b не делится на d.

При b, кратном d, сравнение имеет d решений.

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

Разлагая в непрерывную дробь отношение m:а,