ПРЕДИСЛОВИЕ

Теория сравнений — наука о целых числах, рассматриваемых в их связи с остатками от деления на фиксированное натуральное число, называемое модулем. Созданная трудами Ферма, Эйлера, Лежандра, Лагранжа, К. Гаусса и Дирихле теория сравнений обогатила математику многими новыми понятиями; ее идеи и методы давно вышли за пределы теории чисел и проникли в алгебру, алгебраическую геометрию, теорию кодирования, кибернетику, вычислительную технику.

Возникновение теории сравнений связано с изучением диофантовых уравнений. Ясно, что для разрешимости диофантова уравнения необходима разрешимость соответствующего сравнения по любому модулю. Во многих случаях оказывается, что локальная разрешимость, т. е. разрешимость соответствующего сравнения по всем модулям, является также и достаточным условием для разрешимости диофантова уравнения. Например, справедлива следующая теорема, доказанная Лежандром.

Теорема. Если а, Ь, с— попарно взаимно простые целые числа, свободные от квадратов и не все одного знака, то уравнение

ах² + by² 4- cz² = О

разрешимо в целых числах тогда и только тогда, когда разрешимы сравнения

х² в — be (mod а) у² = — са (mod b) z² = — ab (mod с)

Разрешимость указанных в теореме сравнений для каждого конкретного набора чисел а, Ь, с можно установить хотя бы простым перебором. Следовательно, теорема Лежандра

дает простой и эффективный критерий разрешимости диофантова уравнения ах² + by² + cz² — 0.

Другим примером может служит такое утверждение: целое число вида 4^ + 3 нельзя представить суммой двух квадратов целых чисел. Действительно, если бы это было возможно, то было бы разрешимо сравнение

х² + у² = 3 (mod 4).

Но простая проверка показывает, что последнее сравнение не имеет решений, и мы приходим к противоречию.

Рассмотрение задач подобного рода в дальнейшем привело Гензеля к введению нового типа чисел, названных им р-адическими числами. В настоящее время р-адические числа являются одним из основных инструментов теории чисел и смежных с ней разделов математики.

Другим важным понятием, появлением которого мы обязаны теории сравнений, являются конечные поля (поля Галуа). Сфера их применения с каждым днем расширяется и охватывает не только математику, но и физику, кибернетику, радио и вычислительную технику.

Как самостоятельная наука теория сравнений имеет свои собственные трудные и интересные проблемы. К таким проблемам относится, например, знаменитая гипотеза И. М. Виноградова о распределении квадратичных вычетов и невычетов в натуральном ряде, гипотеза Артина о первообразных корнях и др.

В настоящей брошюре популярно и достаточно полно изложены все основные вопросы теории сравнений, начиная с простейших понятий и определений и кончая самыми последними достижениями. Доступное широкому кругу читателей изложение современного состояния теории сравнений стало возможно благодаря трудам автора С. А. Степанова, создавшего новый арифметический метод, с помощью которого элементарно доказаны все результаты, которые ранее были под силу лишь сложному аппарату алгебраической геометрии.

Книга будет интересна всем, кто любит математику, пытается узнавать новое и размышлять над нерешенными задачами.

Проф. А. А. Карацуба.

Глава 1

ОСНОВНЫЕ ПОНЯТИЯ

1. Мы будем рассматривать целые числа в связи с их остатками от деления на данное положительное число /и, которое назовем модулем. Каждому целому числу а отвечает определенный остаток г = а — mq, 0 г т — 1 от деления его на т\ если двум целым числам а и b отвечает один и тот же остаток г, то они называются равноостаточными по модулю т, или сравнимыми по модулю т. Для обозначения сравнимости чисел а и b употребляется символ а = b (mod т). Ясно, что а = b (mod т) тогда и только тогда, когда разность а— b делится на т. Если а— b не делится на т, то мы говорим, что а и b несравнимы по модулю т, и записываем это следующим образом: а ф. b (mod т).

Отношение сравнимости по модулю т является отношением эквивалентности; оно рефлексивно, так как а = a (mod т) симметрично, поскольку из а == b (mod т) следует b = a (mod m), транзитивно, так как из а= b (mod т) и b = с (mod т) следует а = с (mod т). Тем самым отношение «= (mod m)» разбивает множество всех целых чисел на непересекающиеся классы эквивалентности Я, В, С, ... , причем два целых числа сравнимы между собой по модулю т тогда и только тогда, когда они лежат в одном и том же классе. Эти классы называются классами вычетов по модулю т.

Очевидно, что целые числа 0, 1, ... , т— 1 лежат в разных классах вычетов, и так как каждое целое число сравнимо по модулю т с одним из этих чисел, то имеется точно т классов вычетов по модулю т.

Подобно обычным равенствам сравнения можно складывать, вычитать и перемножать. Если а = b (mod т) и c==d(modm), то а ± с = b ± d (mod т) и ас== в bd (mod т). Действительно, если а— b = mq, с —

— d = mt, то (a — b) ± (c — d) = (q ± t)m. Далее, (a — b)c = mqc, так что ас == be (mod m) и (c — d)b = = mtb, так что be == bd (mod m), откуда по свойству транзитивности яс== bd (mod m).

В общем случае делить сравнения нельзя. Мы имеем 36 г 16 (mod 10), 12 = 2 (mod 10), но 3^8 (mod 10). Однако обе части сравнения можно сократить на множитель, взаимно простой с модулем.

Операции сложения, вычитания и умножения сравнений индуцируют аналогичные операции на множестве классов вычетов. Пусть А и В — два класса вычетов по модулю т. Каковы бы ни были числа а£А и Ь£В (запись а£А означает, что а является элементом множества Л), их сумма а + b всегда лежит в одном и том же классе вычетов С, который мы назовем суммой С' — А Н- В классов А и В. Аналогичным образом определяются разность А — В и произведение АВ двух классов вычетов по модулю т. Для дальнейшего нам потребуются некоторые алгебраические понятия.

Множество G с заданной на нем бинарной операцией ху, ставящей в соответствие каждой паре элементов х, у этого множества некоторый вполне определенный третий элемент z — ху из G, называется группой, если:

1) операция ассоциативна, т. е. (ab)c = а(Ьс) для любых a, b, c£G-,

2) в G существует такой элемент е, называемый единицей, что ае = еа = а для любого a^G',

3) для любого элемента a£G существует такой элемент x£G, называемый обратным к а, что ах = ха = е.

Наряду с указанной выше мультипликативной записью ab групповой операции, называемой умножением, употребляется также аддитивная запись a -f- b, которая называется сложением. В этом случае роль единичного элемента играет нулевой элемент 0 группы G.

Группа G называется абелевой, если имеет место коммутативный закон ab = Ьа для любых элементов a, b£G.

Произведение п элементов, равных а, называется п-й степенью элемента а и обозначается а^п. Наименьшее натуральное число п такое, что а^п — е называется порядком элемента а.

Группа G называется циклической, если она состоит из степеней а^п, п = 0, ±1, ±2, . . . одного и того же элемента а.

абсолютной величине, называется абсолютно наимень- п '^{п  т}

ишм вычетом. При г< — имеем р = г, при г —

т имеем р < г—т\ наконец, если т четное и г = -2~,

„ т т

то за р можно взять любое из двух чисел ~ и — -у.

Взяв из каждого класса вычетов по одному представителю, получим полную систему вычетов по модулю т. Таким образом, множество из т целых чисел образует полную систему вычетов по модулю т тогда и только тогда, когда его элементы несравнимы друг с другом по модулю т. Чаще всего в качестве полной системы вычетов употребляются наименьшие неотрицательные вычеты 0, 1, ... , т— 1 или абслютно наименьшие вычеты, состоящие из т— 1

чисел 0, ± 1, . . . , ± —у в случае нечетного т и чисел т — 2 т т — 2

О, ± 1, . . . , ± 2 » ~2~^или 0, — 1» • • • » ±  2 »

т

-у в случаях четного т.

Классы вычетов по модулю /и, элементы которых взаимно просты с /и, назовем приведенными классами вычетов. Взяв из каждого такого класса по одному вычету, получим приведенную систему вычетов по модулю т. Приведенную систему вычетов можно составить из чисел полной системы вычетов 0, 1, ... , т— 1, взаимно простых с модулем т. Следовательно, приведенная система вычетов по модулю т состоит из <р (т) элементов, где ср (т) — функция, Эйлера, равная количеству неотрицательных целых чисел, меньших т и взаимно простых с т.

Пусть / (х) = а_ох" + а_гх^п~^х + . . . + а_п — многочлен с целыми коэффициентами. Решением сравнения f (х) = 0 (mod т) назовем всякий класс вычетов х = х_г (mod т) такой, что f (х^ = 0 (mod т) для целого числа х_г.

Обозначим через (а, Ь) наибольший общий делитель а и Ь. Если (а, т) = 1 и х пробегает приведенную систему вычетов по модулю т, то ах также пробегает приведенную систему вычетов по модулю т. Действительно, чисел ах столько же, сколько и чисел х, т. е. (р (т). Далее, числа ах несравнимы между собой по модулю т и взаимно просты с т. Следовательно, сравнение ах = l(mod т) имеет единственное решение х== Xi (mod т) такое, что (x_n т) = 1. Другими словами, если А, X — приведенные классы вы

четов и Е — класс вычетов, содержащий число 1, то уравнение АХ = Е разрешимо и тем самым приведенные классы вычетов по модулю т образуют по умножению абелеву группу порядка ф (/п), единичным элементом которой является класс Е.

Далее, если (а, т) = 1 их пробегает приведенную систему вычетов, состоящую из наименьших неотрицательных вычетов г₂, . . . , г_ф(_/Л), то наименьшие неотрицательные вычеты ах состоят из тех же чисел г_х, г₂, . . . , Следовательно,

^r i^r % • • • аг₂ . . . ar_v(ra)(mod т) или

(_аф(т)_ 1)_Г1Гг . . . г_ф(/п)== О (mod /и).

Но г_х, г₂, . . . , г_ф(т) взаимно просты с модулем т, тогда J (mod т). Тем самым нами установлен следующий результат.

Теорема Эйлера. Если а взаимно просто с т, то _а^т) — J (mod т).

Рассмотрим теперь кольцо классов вычетов по простому модулю р. В этом случае все классы вычетов, за исключением нулевого, будут приведенными и, следовательно, образуют по умножению абелеву группу. Таким образом, классы вычетов по простому модулю р образуют конечное поле из р элементов. В дальнейшем мы будем обозначать это поле через F_p и его единичный элемент через 1.

В случае простого модуля р имеет место следующее утверждение, являющееся частным случаем теоремы Эйлера.

Малая теорема Ферма. Если а не делится на простое число p_t то а?~* = 1 (mod р).

Из этой теоремы следует, что аР s a (mod р) для любого целого а. Другими словами, каждый элемент поля классов вычетов по простому модулю р удовлетворяет уравнению х^р — х = 0.

Для дальнейшего выяснения структуры поля классов вычетов по простому модулю р нам потребуется понятие первообразного корня. Первообразным корнем по модулю т называется такое целое число g, что g^^m = 1 (mod т) и g⁶^l (mod т) при 1 ^ф (т) — 1. Существование первообразных корней для всех простых модулей р устанавливает следующая теорема, принадлежащая Гауссу.

Теорема. Имеется ф (р— 1) первообразных корней по простому модулю р.

Доказательство этой теоремы мы приведем в следующем параграфе для более общего случая произвольных конечных полей.

Из теоремы Гаусса следует, что мультипликативная группа поля классов вычетов по простому модулю р является циклической группой порядка р — 1.

2. В заключение главы остановимся на вопросе о количестве решений алгебраических сравнений / (х) == = 0 (mod р) по простому модулю р, где f (х) = а_ох^п + + а₁х^л”¹ + • • • + а_п — многочлен с целыми коэффициентами и а о О (mod р).

Два целочисленных многочлена f (х) и g (х) назовем сравнимыми по модулю р (точнее, их следовало бы называть тождественно сравнимыми), если все коэффициенты их разности f (х) — g (х) делятся на р. Для обозначения сравнимости многочленов f (х) и g (х) мы будем использовать тот же символ / (х) = g (х) (mod р), что и для обозначения сравнимости чисел.

Мы скажем, что класс вычетов x==Xj (mod р) является s-кратным решением сравнения / (х) == О (mod р), если имеет место разложение f (х) = (х— g (х) (mod р), где s 1 и g (х) — многочлен с целыми коэффициентами, такой, что g (x_t) 0 (mod р).

В качестве общего результата о количестве решений сравнения / (х) = 0 (mod р) укажем следующую теорему.

Теорема Лагранжа. Количество решений сравнения f (х) = 0 (mod р) по простому модулю р, взятых с их кратностями, не превосходит степени п многочлена f (х) = а_ох^п + ЯрК"-¹ 4- . . . + а_п, О (mod р).

Теорему легко доказать индукцией по степени п многочлена f (х). Для п = 1 утверждение теоремы очевидно, поскольку (а₀, р) = 1. Если сравнение f (х) s 0 (mod р) степени п 1 имеет s-кратное решение х = x,(mod р), то / (х) = (х — x_t)^sg (х) (mod р), где g (х) — многочлен степени п—s. Следовательно, каждое решение сравнения / (х) = О (mod р) удовлетворяет или сравнению х — х_г = 5= 0 (mod р), которое дает исходное решение х == = Xj (mod р), или сравнению g (х) == 0 (mod р), которое по индуктивному предположению имеет не более п — s решений. Тем самым сравнение f (х) = 0 (mod р) имеет самое большее п решений.

Заметим, что сравнение f (х) = 0 (mod р) мы можем трактовать как уравнение f (х) = 0 над полем классов вычетов по простому модулю р. При такой интерпретации ю

теорема Лагранжа выражает широко известный факт, что число корней не равного нулю многочлена / (х) с коэффициентами из произвольного поля не превосходит степени п многочлена f (х).

Далее, из теорем Лагранжа и Ферма следует, что х^р — х = х (х — 1) . . . (х — р + 1) (modp). Действительно, сравнение х^р — х — х (х — 1) . . . (х — р + 1) в ==0 (mod р) имеет по теореме Ферма р решений, в то время как степень многочлена х^р—х— х (х—1) . . . (х— р + 1) не выше р— 1. Значит, все коэффициенты этого многочлена должны делиться на р. В частности, сравнивая коэффициенты при первой степени х, мы получаем теорему Вильсона', (р— 1)1 =— 1 (mod р).

Рассмотрим теперь двучленные сравнения х^п = a (mod р), где а ^0 (modp). Пусть g—первообразный корень по модулю р и пусть х == g^mod р), а = g^l (mod р). Тогда сравнение х^п = a (mod р) эквивалентно линейному сравнению пу == I (mod р — 1).

Покажем, что линейное сравнение ах== b (mod т) не имеет решений, если b не делится на d = (а, /и), и имеет d решений, если b делится на d. Предположим сначала, что d = 1. В этом случае, когда х пробегает полную систему вычетов по модулю т, произведение ах также пробегает полную систему вычетов и, следовательно, сравнение ах = b (mod т) имеет единственное решение. Пусть d 1. Из равенства ах— b = mq следует, что сравнение ах == b (mod т) разрешимо лишь тогда, когда b делится а b nad. При выполнении этого условия мы имеем х— =

^т  ( ^{а т} \  о ^а

= причем)“5", "^"1 = 1. Значит, сравнение ~^х~ b / т \

-у mod у I имеет единственное решение х == \ /

/ т \

а» х, I mod 1, которое дает d решений х ss х_х (mod /п), т ,  (d. — 1) tn

х = x_f-₍^L~ (mod m), ...» x = x,4- %—(modm)« Отсюда следует справедливость следующего утверждения.

Критерий Эйлера. Пусть р — простое число и q — (п, р — 1). Сравнение х^п == a (mod р) разрешимо р—1

тогда и только тогда, когда a ^q si (modр) и в случае разрешимости имеет q различных решений.

Если сравнение х" = a (mod р), где а 0 (mod р), разрешимо, то а называется вычетом степени п по модулю р. В противном случае а называется невычетом степени п по модулю р. В частности, при п = 2 вычеты и невычеты называются квадратичными, при /2 = 3 — кубическими, при м = 4 — биквадратичными.

Заметим, что если а — квадратичный вычет, то сравнение х² = a (mod р) имеет два решения: х = х₀ (mod р) и х == — х₀ (mod р); если же а делится на р, то сравнение х² = a (mod р) имеет единственное решение: х = 0 (mod р).

Введем, наконец, в рассмотрение символ Лежандра (а \

— , который определяется для всех целых а следующим образом:

I,  если а является квадратичным вычетом по / _а \ модулю р;

I— — • —1, если а является квадратичным невычетом ^{4 7}  по модулю р;

О, если а делится на р.

Если р — нечетное простое число, то для каждого а ф 0 (mod р) мы имеем по теореме Ферма а^р~¹ — 1 = (р— 1  \ / р— 1  \ р—i

а ² —1 Да ² +1 / = ()(modp), причем ^{а 2} —1 и р— 1

а ² +1 не делятся одновременно на р (иначе их разность

2 делилась бы на р). Это замечание позволяет, в случае п = 2, следующим образом переформулировать критерий Эйлера:

р— 1 .

^{а 2} = (-“) (mod р).

/ ab \ / а \( b \

Отсюда мы легко выводим, что I ——) = I — I I —) для любых

I а \ / b \

двух целых а, b и что = при а = b (mod р).

Кроме того, из критерия Эйлера следует, что если g— пер- gt V  ( 8 \  <

ьообразныи корень по модулю р, то1 — I = — 1 и, следовательно, g^y е a²(mod р) тогда и только тогда, когда у является четным числом. Отсюда следует, что среди чисел р — 1

х = 1, 2, . . . , р — 1 имеется в точности “у^- квадратичных вычетов и —%— квадратичных невычетов по простому модулю р 2.

Более полное изложение основных понятий теории сравнений читатель может найти в книге И. М. Виноградова 11].

Глава 2

СРАВНЕНИЯ ПО ДВОЙНОМУ МОДУЛЮ

И КОНЕЧНЫЕ ПОЛЯ

1. Пусть F_p—поле классов вычетов по простому модулю р. Рассмотрим кольцо F_p [х ] многочленов от переменного х с коэффициентами из поля F_p. Элементы поля F_p назовем константами кольца Fp [х 1 и единичный элемент F_p обозначим через 1.

Мы скажем, что многочлен g (х) делится на многочлен f (х) в кольце F_p [х], если существует многочлен h (х) с коэффициентами из F_p, такой, что g (х) = f (х) h (х). Если многочлен [ (х) не имеет других делителей, кроме а/ (х) и а, где а £F_pt то f (х) называется неприводимым многочленом в F_p 1x1. Далее, наибольшим общим делителем двух многочленов f (х) и g (х) называется такой многочлен d (х), который является их общим делителем и вместе с тем делится на любой другой общий делитель этих многочленов. Заметим, что наибольший общий делитель определен с точностью до постоянного множителя аЕГр, а =/= 0. Если многочлены f (х) и g (х) не имеют общих делителей, отличных от констант, то они называются взаимно простыми.

С помощью алгоритма Эвклида легко показать, что если d (х) есть наибольший общий делитель многочленов f (х) и g (х), то в кольце F_p 1х ] можно найти такие многочлены и (х) и v (х), что [ (х)и (х) + g (x)v (х) = d (х), причем если степени многочленов / (х) и g (х) больше нуля, многочлены и (х) и v (х) можно выбрать такими, что степень и (х) меньше степени g (х) , а степень v (х) меньше степени / (х). Отсюда следует, в частности, что если произведение g (х)й (х) многочленов g (х) и h (х) делится в кольце F_p [х] на неприводимый многочлен f (х), то либо g(x)_t либо h (х) делится на f (х). Действительно, если, на- например, f (х) не делит g (х), то f (x)u(x) + g (х)и (х) = 1.

В таком случае h (х) f (х) и (х) + h, (x)g (х) и (х) = h (х), тогда f (х) делит h (х). Как следствие мы получаем отсюда следующий результат: для каждого многочлена а (х) кольца F_p [х ] имеет место разложение а (х) = f _х (х)“< . . . f₃ (x)a_s на неприводимые сомножители (х).............. причем такое разложение с точностью до констант кольца F_p [х] и порядка следования сомножителей единственно.

Назовем два многочлена а (х) и b (х) из кольца F_p [х ] сравнимыми по модулю f (х) = х" + о^х"^-1 4- ... 4- а_я, €/%, если их разность а (х) — b (х) делится на f (х) в кольце F_p [х]. Сравнения такого рода будем называть, следуя Дедекинду, сравнениями по двойному модулю и для обозначения сравнимости а (х) и b (х) по модулю f (х) использовать символ: а (х) = b (х) (mod f (х)).

Отношение сравнимости по двойному модулю рефлексивно, симметрично, транзитивно и поэтому разбивает множество всех многочленов с коэффициентами из F_p на непересекающиеся классы А, В, С, ... , называемые классами вычетов по модулю f (х). Поскольку каждый многочлен а (х) сравним по модулю f (х) с одним и только одним многочленом г (х) вида г (х) = ₽iX^n-1 + р₂х^п“² 4- + . . . 4- Р_п, где р_х, р₂, . . . , р_п независимо друг от друга пробегают элементы поля F_p, то имеется в точности q = рп классов вычетов по модулю f (х).

Сравнения по двойному модулю можно складывать, вычитать и перемножать подобно обычным сравнениям. Эти операции индуцируют аналогичные операции на классах вычетов по модулю f (х), превращая множество классов вычетов по двойному модулю в коммутативное кольцо, нулевым элементом которого служит класс, состоящий из всех кратных многочлена f (х), а единицей — класс вычетов Е, содержащий единичный элемент 1 поля F_p.

Пусть теперь f (х) = х^п + а_хх^п-1 4“ . . . 4- а_п — неприводимый многочлен из кольца F_p [х]. Если многочлен g (х) не делится на f (х), то f (х) и g (х) взаимно просты и, следовательно, в кольце F_p [х ] найдутся такие многочлены и (х) и v (х), причем степень v (х) меньше п, что f (х)и(х) + g (х)и (х) = 1. В таком случае g (х)и(х) = == 1 (mod f (х)) и, стало быть, уравнение АХ = Е, где А — класс вычетов по модулю f (х), состоящий из многочленов, не делящихся на f (х), а Е — единичный элемент кольца вычетов по модулю f (х) имеет единственное решение X — Л^-1.