Математическая энциклопедия - сравнение

соотношение между целыми числами а и и вида a=b+mk, означающее, что их разность а-b делится на заданное целое положительное число т, наз. модулем сравнения; при этом аназ. вычетом целого числа bпо модулю т. Для выражения сравнимости чисел аи bпо модулю тупотребляется символ

Если разность а-b не делится на т, то a и bназ. несравнимыми по модулю ти для выражения несравнимости аи bупотребляется символ

Наличие С. эквивалентно тому, что аи b имеют одинаковые остатки при делении на т.

Отношение сравнимости по фиксированному модулю m является отношением эквивалентности: оно рефлексивно, т. к. симметрично, т. к. из следует и транзитивно, т. к. из и следует, что Тем самым отношение разбивает множество всех целых чисел на непересекающиеся классы эквивалентности А, В, С, . . . Два целых числа лежат в одном и том же классе тогда и только тогда, когда они сравнимы по модулю т. Эти классы наз. классами вычетов по модулю т. Каждое целое число сравнимо по модулю тлишь с одним из чисел 0, 1, . . ., т -1; числа 0, 1, . . ., т-1 лежат в различных классах, поэтому имеется в точности . классов вычетов, а числа 0, 1, . . ., т-1 образуют множество представителей этих классов. Любое множество из тцелых чисел, взятых по одному из каждого класса вычетов, наз. полной системой вычетов по модулю т.

С. с одним и тем же модулем можно складывать, вычитать и перемножать подобно обычным равенствам, т. е. из

и

следует, что

и

Обе части С. можно умножить на одно и то же целое число, обе части С. можно разделить на их общий делитель, если последний взаимно прост с модулем С. Если же общий делитель числа, на к-рое делятся обе части С., и модуля С. тесть d, то после деления на dполучается С. по модулю m/d.

Операции сложения, вычитания и умножения С. индуцируют подобные же операции над классами вычетов. Так, если . и bпроизвольные элементы из классов вычетов Аи В соответственно, то а+b всегда лежит в одном и том же классе вычетов, наз. суммой А+В классов Аи В. Аналогично определяется разность А-В и произведение Ах В двух классов вычетов Аи В. Классы вычетов по модулю тобразуют по сложению абелеву группу порядка т. Нулевым элементом этой группы является класс, состоящий из всех целых чисел, кратных числу т;обратным к классу Аявляется класс А, состоящий из всех элементов класса А, взятых со знаком минус. Более того, классы вычетов по модулю тобразуют кольцо относительно определенных выше операций сложения, вычитания и умножения.

Пусть F(x1, x2, . . ., х п) - многочлен от ппеременных с целыми коэффициентами. Выражение вида

наз. алгебраическим сравнением. Решением сравнения (*) наз. всякий набор а 1, а 2, . . ., а n целых значений неизвестных x1, x2, . . ., х п такой, что число F(a1, а2, . . ., а п )сравнимо с нулем по модулю т. Если а i, лежат соответственно в классах вычетов Xi по модулю т, то любой другой набор где также будет решением С. Поэтому принято наз. решением С. (*) также сам набор классов вычетов, представителями к-рых являются a1, a2, . . ., а п. т. е. решение алгебраического уравнения F(x1, x2, . . ., х п) =0вкольце классов вычетов по модулю т. При таком соглашении С. (*) будет иметь столько решений, сколько наборов классов вычетов полной системы по модулю тудовлетворяют уравнению .(x1, x2, . . ., х п)=0. Аналогично определяется число решений С. более общего вида, а также систем С. С. 1-й степени

если авзаимно просто с т(что обозначается ( а, т)=1), имеет единственное решение. Классы вычетов по модулю т, элементы к-рых взаимно просты с т, образуют абелеву группу по умножению. Единицей этой группы является класс Е, содержащий число 1, и обратным к классу Аявляется класс А ^-1, содержащий решение x С.

Классы вычетов по модулю т, элементы к-рых взаимно просты с т, наз. приведенными классами, а любая система чисел, взятых по одному из каждого приведенного класса, наз. приведенной системой вычетов. Приведенная система вычетов состоит из элементов, где Эйлера функция, указывающая количество чисел в множестве 1, 2, . . ., т, взаимно простых с т.

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

Теорема Эйлера. Если а и m взаимно просты, то

(см. Эйлера теорема).

Частный случай этой теоремы для простого модуля теорема Ферма: если р - простое число и ане делится на р, то

(см. Ферма малая теорема).

Важным понятием для изучения мультипликативной группы приведенных классов вычетов является понятие первообразного корня по модулю т. При (a, m) = l существуют положительные целые с условием напр. Наименьшее из них наз. показателем, к-рому принадлежит число а по модулю т.

Числа, принадлежащие показателю (если такие существуют), наз. первообразными корнями по модулю т. Если g - первообразный корень по модулю ти пробегает полную систему вычетов по модулю то пробегает приведенную систему вычетов по модулю т. Таким образом, если (а, m)=1, то при нек-ром из множества 0, 1, . . ., имеет место С. Такое наз. индексом числа а по модулю т при основании gи обозначается символом ind a или, более точно, indg а. Свойства индекса во многом аналогичны свойствам логарифма. Первообразные корни существуют только для модулей т>1 вида где простое число и целое. В этих случаях мультипликативная группа приведенных классов вычетов по модулю тимеет наиболее простую структуру, являясь циклической группой порядка В остальных случаях группы приведенных классов вычетов устроены значительно сложнее.

Многие задачи теории чисел сводятся к вопросу о разрешимости или неразрешимости того или иного типа С. Ввиду этого теория С., впервые систематически изложенная К. Гауссом (см. [5]) и поставленная им в основу классической теории чисел, до сих пор является одним из основных средств при решении теоретико-числовых задач. В этой связи фундаментальное значение для теории чисел имеет исследование вопроса о числе решений алгебраич. С. Простейшим типом ал-гебраич. С. являются С. 1-й степени с одним неизвестным Полный ответ на вопрос о числе решений С. 1-й степени дает следующая теорема. Пусть (a, m)=d. Сравнение неразрешимо, если b не делится на d. При b, кратном d, С. имеет ровно dрешений.

Вопрос о разрешимости системы линейных С.

по простому модулю р>2 полностью решается в общей теории линейных уравнений над произвольными полями. Случай составного модуля можно свести к случаю простого модуля.

Следующим по сложности изучения видом алгебраич. С. c.одним неизвестным является двучленное сравнение

при ( а, т)=1.

Если С. имеет решения, то a наз. вычетом степени n по модулю т. В противном случае аназ. невычетом степени n по модулю т. В частности, при п=2 вычеты или невычеты называются квадратичными, при п=3 кубическими, а при n=4 биквадратичными.

Вопрос о числе решений С.

а (х)=0(mod m)

по составному модулю сводится к вопросу о числе решений С.

для каждого i=l, 2, . . ., s. Имеет место следующая теорема: если m1, . . ., т r - попарно взаимно простые целые положительные числа, то число . решений С. выражается через величины Ni, i= 1, 2, .. ., r, равные числу решений соответствующих С. по формуле В свою очередь, вопрос o числе решений С.

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

Аналогичная ситуация имеет место и в случае алгебраич. С. от нескольких переменных, т. е. в невырожденных случаях вопрос о числе решений С. F(x1,, . . ., х п)=0(mod m) по составному модулю m редуцируется к вопросу о числе решений такого же С. по простому модулю.

Верхнюю границу для числа решений С. где дает теорема Лагранжа: число решений С. не превосходит степени многочлена f(x). Изучение вопроса о точном числе решений С. в общем случае встречает значительные трудности, и в этом направлении к настоящему времени (1984) получены лишь немногие результаты.

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

При изучении квадратичных С.

по простому модулю ри для их приложений вводятся Лежандра символ и Якоби символ.

Алгебраич. С. по простому модулю с двумя неизвестными (и вообще с любым числом неизвестных)

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

для числа Np решений широкого класса С. Такая же асимптотика была впоследствии выведена методами теории чисел без выхода за рамки теории С. (см. [6]).

Об алгебраич. С. от многих неизвестных известно сравнительно мало. В качестве общего результата можно привести следующее (теорема Шевалле). Пусть F(x1,, . . ., х п) многочлен с целыми рациональными коэффициентами, степень к-рого меньше п. Тогда число решений С.

делится на простое число р. Сильный результат в этом круге вопросов получен П. Делинем [9] (см. также [10]).

Большое значение имеет также исследование вопроса о числе решений С. на неполной системе вычетов. Систематич. решение этого вопроса было начато работами И. М. Виноградова (см. [4]). В качестве примера задач такого типа может служить задача о распределении квадратичных вычетов и невычетов во множестве 1, 2, . . ., р-1, связанная с изучением решений С. (см. Виноградова гипотезы, Распределение степенных вычетов и. невычетов).

Лит.:[1] Боревич Э. И., Шафаревич И. Р., Теория чисел, 2изд., М., 1972; [2] Венков Б. А., Элементарная теория чисел, М.-Л., 1937; [3] Виноградов И. М., Основы теории чисел, 8 изд., М., 1972; [4] Виноградов И. М., Избр. труды, М., 1952; [5] Гаусс К. Ф., Труды по теории чисел, пер. с нем., М., 1959; [6] Степанов С. А., лТр. Матем. ин-та АН СССР

Математическая энциклопедия. — М.: Советская энциклопедия

И. М. Виноградов

1977—1985