* Данный текст распознан в автоматическом режиме, поэтому может содержать ошибки
МЕТОД СРАВНЕНИЙ
!
285
ремы ) . Это новое доказательство удовлетворительнее прежнего, так как оно не только доказывает существование решения, но дает метод фактического получения всех решений уравнения (10). Метод этот, однако, не является, как мы уже заметили, кратчайшим из возмож ных; и в следующей главе мы в третий раз вернемся к этой задаче, чтобы дать уже практически наилучшее ее решение. Обратимся теперь к случаю, когда наибольший общий делитель d чисел а и т больше 1: (a, m)=d^> 1. Пусть a=da\ m=dm, так что (а\ взаимно просты). Если b не делится сравнение (7) вовсе не может иметь какое-нибудь число х удовлетворяет ах — b=my, b = ax— т')=1 (т. е. числа а и т' на d, то, как легко видеть, решени^. В самом деле, если этому сравнению, то (a'V—т'у),
9 1
my=d
т. е. b должно быть кратно d. Если же Ъ делится на d то пусть b=db*\ делимость ах—b=d(a'x — b') на m=dm' равносильна делимости а'х — V на т' т. е. сравнение (7) равносильно сра внению a'x=b (modт).
9 f
Но это последнее сравнение, в котором (а' т ' ) = 1 , имеет, как мы уже знаем, в точности одно решение по модулю т'; другими словами, числа, удовлетворяющие сравнению (7), в рассматриваемом , т случае образуют один класс по модулю т ; но легко видеть, что один класс по модулю т распадается на d классов по мо дулю т\ в самом деле, если этот класс по модулю т записать в виде x -j-m'z где z — любое целое число, то, очевидно, числа этого класса
9 0 9
*о> * о + « ' р х + 2т' x -\-(d— l)m будут все разных классов по модулю т дальше же пойдут повто рения: дг -\-dm =х -]-т = х (modт)
0 9 0 9 0 0 0 9
f
x -\-(d1)т'=х -\-т-\-т'
0 0
= х -\-т'
0
(тойт)
9
и т. д. Согласно принятой нами терминологии мы должны сказать, что в этом случае сравнение (7) имеет d решений. Таким образом, вопрос о числе решений сравнения (7) первой степени с одним неизвестным нами теперь разобран до конца. Общий ') То обстоятельство, что это новое доказательство содержит ссылку на теорему 2 гл. I , не создаёт, конечно, ложного круга, так как в гл. I мы показали (стр. 261), что теорема 2 может быть доказана независимо от теоремы 1.
