МЕТОД СРАВНЕНИЙ

285

ремы 1). Это новое доказательство удовлетворительнее прежнего, так

как оно не только доказывает существование решения, но дает метод

фактического получения всех решений уравнения (10). Метод этот,

однако, не является, как мы уже заметили, кратчайшим из возмож-

ных; и в следующей главе мы в третий раз вернемся к этой задаче,

чтобы дать уже практически наилучшее её решение.

Обратимся теперь к случаю, когда наибольший общий делитель d

чисел а и т больше 1:

Пусть так что (а', (т. е. числа а' и nz'

взаимно просты). Если Ь не делится на а, то, как легко видеть,

срдвнение (7) вовсе не может иметь решении. В самом деле, если

какое-нибудь число х удовлетворяет этому сравнению, то

ах—Ь (а'У—т'у),

т. е. Ь должно быть кратно d. Если же Ь делится на d, то пусть

Ь делимость (a'x—b') на равносильна

делимости a'x—b' на т. е- сравнение (7) равносильно сра-

внению

а'х (mod

Но это последнее сравнение, в котором (а', 1, имеет, как

мы уже знаем, - в точности одно решение по модулю т'; другими

словами, числа, удовлетворяющие сравнению (7), в рассматриваемом

случае образуют один класс по модулю т'

но легко видеть,

что один класс по модулю т' распадается на d классов по мо-

дулю т; в самом деле, если этот класс по модулю т' записать

в виде где г— любое целое число, то, очевидно, числа

этого класса

Хо, Хо-{-т', хо-А—2т',

будут все разных классов по модулю т, дальше же пойдут повто-

рения:

Хо dT' Т (mod Т),

Хо + (d + 1) т' = хо-}-т' (mod т),

и т. д. Согласно принятой нами терминологии мы должны сказать,

что в этом случае сравнение (7) имеет d решений.

Таким образом, вопрос о числе решений сравнения (7) первой

степени с одним неизвестным нами теперь разобран до конца. Общий

1) То обстоятельство, что это новое доказательство содержит ссылку

на тео1М.ау 2 гл. 1, не создаёт, конечно, ложного круга, так как в гл.

мы показали (стр. 261), что теорема 2 может быть доказана независимо от

теоремы 1.