Сравнение

соотношение между целыми числами а и и вида a=b+mk, означающее, что их разность а-b делится на заданное целое положительное число т, наз. модулем сравнения; при этом аназ. вычетом целого числа bпо модулю т. Для выражения сравнимости чисел аи bпо модулю тупотребляется символ [img: http://localhost:8080/file/051948-1.jpg] Если разность а-b не делится на т, то a и bназ. несравнимыми по модулю ти для выражения несравнимости аи bупотребляется символ [img: http://localhost:8080/file/051948-2.jpg] Наличие С. [img: http://localhost:8080/file/051948-3.jpg] эквивалентно тому, что аи b имеют одинаковые остатки при делении на т. Отношение сравнимости по фиксированному модулю m является отношением эквивалентности: оно рефлексивно, т. к. [img: http://localhost:8080/file/051948-4.jpg] симметрично, т. к. из [img: http://localhost:8080/file/051948-5.jpg] [img: http://localhost:8080/file/051948-6.jpg] следует [img: http://localhost:8080/file/051948-7.jpg] и транзитивно, т. к. из [img: http://localhost:8080/file/051948-8.jpg] и [img: http://localhost:8080/file/051948-9.jpg] следует, что [img: http://localhost:8080/file/051948-10.jpg] Тем самым отношение [img: http://localhost:8080/file/051948-11.jpg] разбивает множество всех целых чисел на непересекающиеся классы эквивалентности А, В, С,... Два целых числа лежат в одном и том же классе тогда и только тогда, когда они сравнимы по модулю т. Эти классы наз. классами вычетов по модулю т. Каждое целое число сравнимо по модулю тлишь с одним из чисел 0, 1,..., т -1; числа 0, 1,..., т-1 лежат в различных классах, поэтому имеется в точности. классов вычетов, а числа 0, 1,..., т-1 образуют множество представителей этих классов. Любое множество из тцелых чисел, взятых по одному из каждого класса вычетов, наз. полной системой вычетов по модулю т. С. с одним и тем же модулем можно складывать, вычитать и перемножать подобно обычным равенствам, т. е. из [img: http://localhost:8080/file/051948-12.jpg] и [img: http://localhost:8080/file/051948-13.jpg] следует, что [img: http://localhost:8080/file/051948-14.jpg] и [img: http://localhost:8080/file/051948-15.jpg] Обе части С. можно умножить на одно и то же целое число, обе части С. можно разделить на их общий делитель, если последний взаимно прост с модулем С. Если же общий делитель числа, на к-рое делятся обе части С., и модуля С. тесть d, то после деления на dполучается С. по модулю m/d. Операции сложения, вычитания и умножения С. индуцируют подобные же операции над классами вычетов. Так, если. и bпроизвольные элементы из классов вычетов Аи В соответственно, то а+b всегда лежит в одном и том же классе вычетов, наз. суммой А+В классов Аи В. Аналогично определяется разность А-В и произведение Ах В двух классов вычетов Аи В. Классы вычетов по модулю тобразуют по сложению абелеву группу порядка т. Нулевым элементом этой группы является класс, состоящий из всех целых чисел, кратных числу т;обратным к классу Аявляется класс А, состоящий из всех элементов класса А, взятых со знаком минус. Более того, классы вычетов по модулю тобразуют кольцо относительно определенных выше операций сложения, вычитания и умножения. Пусть F(x1, x2,..., х п) - многочлен от ппеременных с целыми коэффициентами. Выражение вида [img: http://localhost:8080/file/051948-16.jpg] наз. алгебраическим сравнением. Решением сравнения (*) наз. всякий набор а 1, а 2,..., а n целых значений неизвестных x1, x2,..., х п такой, что число F(a1, а2,..., а п)сравнимо с нулем по модулю т. Если а i, [img: http://localhost:8080/file/051948-17.jpg] [img: http://localhost:8080/file/051948-18.jpg] лежат соответственно в классах вычетов Xi по модулю т, то любой другой набор [img: http://localhost:8080/file/051948-19.jpg] где [img: http://localhost:8080/file/051948-20.jpg] также будет решением С. Поэтому принято наз. решением С. (*) также сам набор классов вычетов, представителями к-рых являются a1, a2,..., а п. т. е. решение алгебраического уравнения F(x1, x2,..., х п) =0вкольце классов вычетов по модулю т. При таком соглашении С. (*) будет иметь столько решений, сколько наборов классов вычетов полной системы по модулю тудовлетворяют уравнению.(x1, x2,..., х п)=0. Аналогично определяется число решений С. более общего вида, а также систем С. С. 1-й степени [img: http://localhost:8080/file/051948-21.jpg] если авзаимно просто с т(что обозначается (а, т)=1), имеет единственное решение. Классы вычетов по модулю т, элементы к-рых взаимно просты с т, образуют абелеву группу по умножению. Единицей этой группы является класс Е, содержащий число 1, и обратным к классу Аявляется класс А -1, содержащий решение x С. [img: http://localhost:8080/file/051948-22.jpg] Классы вычетов по модулю т, элементы к-рых взаимно просты с т, наз. приведенными классами, а любая система чисел, взятых по одному из каждого приведенного класса, наз. приведенной системой вычетов. Приведенная система вычетов состоит из [img: http://localhost:8080/file/051948-23.jpg] элементов, где [img: http://localhost:8080/file/051948-24.jpg] - Эйлера функция, указывающая количество чисел в множестве 1, 2,..., т, взаимно простых с т. Строение мультипликативной группы приведенных классов вычетов по модулю тв значительной степени выясняют теоремы Эйлера и Ферма, показывающие, что порядок любого ее элемента делит величину [img: http://localhost:8080/file/051948-25.jpg] Теорема Эйлера. Если а и m взаимно просты, то [img: http://localhost:8080/file/051948-26.jpg] (см. Эйлера теорема). Частный случай этой теоремы для простого модуля - теорема Ферма: если р - простое число и ане делится на р, то [img: http://localhost:8080/file/051948-27.jpg] (см. Ферма малая теорема). Важным понятием для изучения мультипликативной группы приведенных классов вычетов является понятие первообразного корня по модулю т. При (a, m) = l существуют положительные целые [img: http://localhost:8080/file/051948-28.jpg] с условием [img: http://localhost:8080/file/051948-29.jpg] [img: http://localhost:8080/file/051948-30.jpg] напр. [img: http://localhost:8080/file/051948-31.jpg] Наименьшее из них наз. показателем, к-рому принадлежит число а по модулю т. Числа, принадлежащие показателю [img: http://localhost:8080/file/051948-32.jpg] (если такие существуют), наз. первообразными корнями по модулю т. Если g - первообразный корень по модулю ти [img: http://localhost:8080/file/051948-33.jpg] пробегает полную систему вычетов по модулю [img: http://localhost:8080/file/051948-34.jpg] то [img: http://localhost:8080/file/051948-35.jpg] пробегает приведенную систему вычетов по модулю т. Таким образом, если (а, m)=1, то при нек-ром [img: http://localhost:8080/file/051948-36.jpg] из множества 0, 1,..., [img: http://localhost:8080/file/051948-37.jpg] имеет место С. [img: http://localhost:8080/file/051948-38.jpg] Такое [img: http://localhost:8080/file/051948-39.jpg] наз. индексом числа а по модулю т при основании gи обозначается символом ind a или, более точно, indg а. Свойства индекса во многом аналогичны свойствам логарифма. Первообразные корни существуют только для модулей т>1 вида [img: http://localhost:8080/file/051948-40.jpg] [img: http://localhost:8080/file/051948-41.jpg] где [img: http://localhost:8080/file/051948-42.jpg] - простое число и [img: http://localhost:8080/file/051948-43.jpg] - целое. В этих случаях мультипликативная группа приведенных классов вычетов по модулю тимеет наиболее простую структуру, являясь циклической группой порядка [img: http://localhost:8080/file/051948-44.jpg] В остальных случаях группы приведенных классов вычетов устроены значительно сложнее. Многие задачи теории чисел сводятся к вопросу о разрешимости или неразрешимости того или иного типа С. Ввиду этого теория С., впервые систематически изложенная К. Гауссом (см. [5]) и поставленная им в основу классической теории чисел, до сих пор является одним из основных средств при решении теоретико-числовых задач. В этой связи фундаментальное значение для теории чисел имеет исследование вопроса о числе решений алгебраич. С. Простейшим типом ал-гебраич. С. являются С. 1-й степени с одним неизвестным [img: http://localhost:8080/file/051948-45.jpg] Полный ответ на вопрос о числе решений С. 1-й степени дает следующая теорема. Пусть (a, m)=d. Сравнение [img: http://localhost:8080/file/051948-46.jpg] неразрешимо, если b не делится на d. При b, кратном d, С. имеет ровно dрешений. Вопрос о разрешимости системы линейных С. [img: http://localhost:8080/file/051948-47.jpg] по простому модулю р>2 полностью решается в общей теории линейных уравнений над произвольными полями. Случай составного модуля можно свести к случаю простого модуля. Следующим по сложности изучения видом алгебраич. С. c.одним неизвестным является двучленное сравнение [img: http://localhost:8080/file/051948-48.jpg] при (а, т)=1. Если С. [img: http://localhost:8080/file/051948-49.jpg] имеет решения, то a наз. вычетом степени n по модулю т. В противном случае аназ. невычетом степени n по модулю т. В частности, при п=2 вычеты или невычеты называются квадратичными, при п=3 - кубическими, а при n=4 - биквадратичными. Вопрос о числе решений С. а (х)=0(mod m) по составному модулю [img: http://localhost:8080/file/051948-50.jpg] сводится к вопросу о числе решений С. [img: http://localhost:8080/file/051948-51.jpg] для каждого i=l, 2,..., s. Имеет место следующая теорема: если m1,..., т r - попарно взаимно простые целые положительные числа, то число. решений С. [img: http://localhost:8080/file/051948-52.jpg] выражается через величины Ni, i= 1, 2,..., r, равные числу решений соответствующих С. [img: http://localhost:8080/file/051948-53.jpg] по формуле [img: http://localhost:8080/file/051948-54.jpg] В свою очередь, вопрос o числе решений С. [img: http://localhost:8080/file/051948-55.jpg] в основном сводится к вопросу о числе решений С. [img: http://localhost:8080/file/051948-56.jpg] по простому модулю р. Основой для такого сведения служит следующая теорема: всякое решение [img: http://localhost:8080/file/051948-57.jpg] сравнения [img: http://localhost:8080/file/051948-58.jpg] единственным образом продолжается до решения [img: http://localhost:8080/file/051948-59.jpg] сравнения [img: http://localhost:8080/file/051948-60.jpg] если только формальная производная [img: http://localhost:8080/file/051948-61.jpg] т. е. найдется единственное решение [img: http://localhost:8080/file/051948-62.jpg] С. [img: http://localhost:8080/file/051948-63.jpg] такое, что [img: http://localhost:8080/file/051948-64.jpg] Аналогичная ситуация имеет место и в случае алгебраич. С. от нескольких переменных, т. е. в невырожденных случаях вопрос о числе решений С. F(x1,,..., х п)=0(mod m) по составному модулю m редуцируется к вопросу о числе решений такого же С. по простому модулю. Верхнюю границу для числа решений С. [img: http://localhost:8080/file/051948-65.jpg] [img: http://localhost:8080/file/051948-66.jpg] где [img: http://localhost:8080/file/051948-67.jpg] [img: http://localhost:8080/file/051948-68.jpg] [img: http://localhost:8080/file/051948-69.jpg] дает теорема Лагранжа: число решений С. [img: http://localhost:8080/file/051948-70.jpg] не превосходит степени многочлена f(x). Изучение вопроса о точном числе решений С. [img: http://localhost:8080/file/051948-71.jpg] в общем случае встречает значительные трудности, и в этом направлении к настоящему времени (1984) получены лишь немногие результаты. Утверждение теоремы Лагранжа перестает быть верным для составного модуля. Указанное специфическое свойство простых чисел объясняется тем, что классы вычетов но простому модулю р образуют поле (см. Сравнение по простому модулю). Другое специфическое свойство простых чисел, объясняемое тем же фактом, выражает Вильсона теорема. При изучении квадратичных С. [img: http://localhost:8080/file/051948-72.jpg] по простому модулю ри для их приложений вводятся Лежандра символ и Якоби символ. Алгебраич. С. по простому модулю с двумя неизвестными (и вообще с любым числом неизвестных) [img: http://localhost:8080/file/051948-73.jpg] можно трактовать как уравнения над простым конечным полем из рэлементов. Поэтому для их изучения наряду с методами теории чисел применяются методы теории алгебраич. функций и алгебраич. геометрии. Именно этими методами была впервые получена асимптотика вида [img: http://localhost:8080/file/051948-74.jpg] для числа Np решений широкого класса С. [img: http://localhost:8080/file/051948-75.jpg] [img: http://localhost:8080/file/051948-76.jpg] Такая же асимптотика была впоследствии выведена методами теории чисел без выхода за рамки теории С. (см. [6]). Об алгебраич. С. от многих неизвестных известно сравнительно мало. В качестве общего результата можно привести следующее (теорема Шевалле). Пусть F(x1,,..., х п) - многочлен с целыми рациональными коэффициентами, степень к-рого меньше п. Тогда число решений С. [img: http://localhost:8080/file/051948-77.jpg] делится на простое число р. Сильный результат в этом круге вопросов получен П. Делинем [9] (см. также [10]). Большое значение имеет также исследование вопроса о числе решений С. на неполной системе вычетов. Систематич. решение этого вопроса было начато работами И. М. Виноградова (см. [4]). В качестве примера задач такого типа может служить задача о распределении квадратичных вычетов и невычетов во множестве 1, 2,..., р-1, связанная с изучением решений С. [img: http://localhost:8080/file/051948-78.jpg] (см. Виноградова гипотезы, Распределение степенных вычетов и. невычетов).