§ 4. Теоремы Эйлера и Ферма; сравнения первой степени.

Если разность двух чисел делится на число с то говорят, что а сравнимо с по модулю и пишут: или просто а Сравнения с одним и тем же модулем можно складывать, вычитать, перемножать и сокращать (на множитель, взаимно простой с модулем), благодаря чему операции над сравнениями имеют большую аналогию с действиями над уравнениями. Знак сравнения был введен Гауссом 20 (D. A., art. 2) и оказался чрезвычайно удобным символом для передачи

арифметических рассуждений. Пусть к — целое число, большее нуля; объединим в один класс все числа, сравнимые с одним и тем же числом по модулю к (термин "класс" принадлежит Гауссу, Theoria residuorum biquadraticorum, II, art. 42, см. 20, стр. 551). Так как для каждого числа а имеем а где - одно из чисел и эти числа несравнимы по модулю к, то видим, что существует к различных классов для модуля к. Выбрав по одному представителю из каждого класса, получим систему к чисел, называемую полной системой вычетов по модулю к; такую систему составляют, например, числа Если одно число класса взаимно просто с то и все числа этого класса обладают тем же свойством; таких классов будет, очевидно, Взяв по одному представителю от каждого из этих классов, получим приведенную систему вычетов по модулю к; таковы, например, при к простом числа к — 1.

Пусть пробегает приведенную систему вычетов по модулю тогда произведения будут несравнимы по модулю к, так как из вытекает Кроме того, числа взаимно простые с к; следовательно, эти числа сравнимы по модулю к с числами х, взятыми только в другом порядке. Сравнивая произведения тех и других чисел по модулю к, приходим к важной теореме Эйлера стр. 274):

Теорема 3. Для всякого числа а, взаимно простого с данным числом имеет место сравнение

В частности, для простого и для а, не делящегося на имеем

Эта теорема, одна из самых важных в теории чисел, была найдена Ферма. Эйлер доказал ее несколькими способами и обобщил на случай составного модуля к.

Из рассуждения, которым мы пользовались при доказательстве теоремы Эйлера, вытекает и другой результат: сравнение первой степени при взаимно простых с к имеет только одно решение относительно х (считая все числа одного и того же класса за одно решение). При обобщении на случай любых § 22) получается теорема: для возможности сравнения необходимо, чтобы делилось на и в этом случае оно имеет 8 несравнимых по модулю к решений относительно Что касается отыскания самих решений х сравнения то эти решения могут быть получены по правилу § 1 при помощи непрерывных дробей, ввиду того, что рассматриваемое сравнение эквивалентно неопределенному уравнению

При перенесении различных теорем теории чисел, доказанных для простых модулей, на составные модули, нужно решение следующей задачи: найти все числа X, удовлетворяющие системе сравнений где — положительные, а — произвольные целые числа. Особенно важен частный случай, когда модули а, с попарно взаимно простые; в этом случае указанная система сравнений всегда имеет решения,

и числа X, ей удовлетворяющие, образуют один класс по модулю (L.-Dirichlet 25).

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