? Говорят, что a сравнимо с b по модулю n , если a?b делится на n . Это обозначают так: a ? b (mod n ). С. имеют много сходства с равенствами. Если f ( x ) целая функция с целыми коэффициентами и а ? b (mod n ), то f ( a ) ? f ( b ) (mod n ). Решить С. f ( x ) ? 0 (mod n ) значит найти, какое число надо подставить вместо x для того, чтобы удовлетворить С. Если f ( a ) делится на n , то данному С. удовлетворяют и все числа сравнимые с a по модулю n . Условились, совокупность всех таких чисел называть одним решением данного С. Говорят, что f ( x ) ? ? 0 (mod n ) имеет m решений, если ему удовлетворяют m чисел несравнимых между собой по модулю п .
Перечислим несколько теорем, относящихся к С.
С. первой степени ax ? b (mod n ) возможно, если b делится на d , наибольшего делителя чисел a и b , и имеет d решений. Если n простое число и a не делится на n , то
a n? 1 ? 1 (mod n ) (теорема Фермата).
Если n простое число, то
1.2.3...( n? 1) ? ? 1 (mod n );
если же n ? составное, то 1.2.3...( n? 1)+1 не делится на n (теорема Вильсона). С. второй степени x 2 ? q (mod p ) при простом модуле возможно и имеет два решения, если q ( p ?1)/2 ? 1 (mod p ); С. невозможно, если q ( p ?1)/2 ? ?1 (mod p ).
Эти два случая различаются при помощи особого вычисления, предложенного Лежандром и усовершенствованного Якоби. Вычисление выполняется очень быстро даже для больших значений p и q.
С. m -ой степени при простом модуле не может иметь более m решений (теорема Лагранжа).
С. x m ? q (mod p ) при простом модуле возможно и имеет d решений, если q ( p ?1)/ d ? 1 (mod p ). Здесь d наибольший делитель чисел m и p? 1.
Для всякого простого числа p существует такое число g , называемое его первообразным корнем , что числа g , g 2 , g 3 ... g p? 1 несравнимы между собой по модулю р .
Если g a ? а (mod p ), то a называется указателем (index) числа a при основании g. Это обозначают так: a = ind a , причем основание подразумевается.
В "Теории С." П. Л. Чебышева приложена таблица указателей для всех простых чисел меньших 200. В сочинении C. G. J. Jacobi, "Canon Arithmeticus", эти таблицы доведены до 1000.
При помощи указателей решаются С. на основании теоремы:
ind ( a b ) ? ind a + ind b (mod p? 1)
напоминающей свойства логарифмов.
Важнейшие сочинения, относящиеся к теории С.: Gauss, "Disquisitiones arithmeticae" (Лейпциг, 1801, "Gauss Werke", т. I; это сочинение издано в Берлине в 1889 г. в переводе на немецкий язык); Serret, "Cours d'alg èbre supe rieure" (т. II, секц. III, П., 1879); Dedekind, "Vorlesungen uber Zahlentheorie vo n Lejeune-Dirichlet" (Брауншвейг, 1894; в 1899 г. в СПб. появился первый выпуск этого сочинения в переводе на русский язык); П. Л. Чебышев, "Теория С." (СПб., 1849; 2-е изд., СПб., 1879); Ю. В. Сохоцкий, "Высшая алгебра" (ч. II-я, СПб., 1888).
Д. С.