* Данный текст распознан в автоматическом режиме, поэтому может содержать ошибки

284 ЭЛЕМЕНТЫ ТЕОРИИ ЧИСЕЛ т г и мы непосредственно видим, что число Ьа^( )' удовлетворяет сравнению (7); так как единственность решения уже установлена, то полное решение сравнения (7) даётся формулой Х = ЬоУ( )т г (mod т). (8) Очевидно, рассматриваемый нами частный случай всегда имеет место, если т есть простое число. В самом деле, число а, которое по самому определению степени сравнения не должно делиться на т будет при этом условии взаимно просто с т; таким образом, еравнение первой степени по простому модулю всегда имеет в точ­ ности одно решение, даваемое в силу теоремы Ферма формулой 9 Х=Ьа ~^ т (mod т) (9) [надо только иметь в виду, что практически отыскание решений с помощью формул (8) или (9) в большинстве случаев не является кратчайшим путём к цели; кратчайший путь даётся алгориф­ мом Евклида, см. главу I I I ] . Мы видим, что и в этом вопросе сра­ внения по простому модулю подчиняются законам, вполне анало­ гичным соответствующим законам теории уравнений. Решениями сравнения (7) служат числа X, для которых раз­ ность ах — Ь делится на т т. е. имеет вид ту, где у — также целое число. Поэтому задача решения сравнения (7) равносильна задаче решения в целых числах х, у уравнения 9 ах—Ь—ту, или, что то же, ах—ту = Ь. (10) Это есть общий вид уравнения первой степени с двумя неизвест­ ными. Мы видим, таким образом, что все результаты теории сра­ внений первой степени с одним неизвестным могут быть истолко­ ваны и вне теории сравнений как законы «неопределённого» или «диофантова» анализа (т. е. учения о решении уравнений в целых числах) первой степени с двумя неизвестными. В частности, основ­ ной полученный нами результат может, очевидно, быть сформули­ рован следующим образом: Если числа а и т взаимно просты, то уравнение (10) всегда может быть решено в целых числах', если (х , у ) есть одно из его решений, то все решения даются формулами г 0 0 х=х -{0 mk, у =у 0 + ak, где k—любое целое число. В частности, при Ь=\ задача решения уравнения (10) (при взаимно простых акт) уже рассматривалась нами в главе I . Там мы доказали (теорема 1) существование решения методом Гаусса. Теперь мы имеем второе доказательство той же тео-