2.3.2. Целые числа по модулю m и алгоритм в грекокитайской теореме об остатках

Вспомним, что при фиксированном по определению а тогда и только тогда, когда для некоторого q (иначе говоря, b содержится в арифметической прогрессии ), или, на языке этой главы, тогда и только тогда, когда делит b — а. Вместо записи мы будем также использовать запись которая читается «6 равно а по модулю или «6 сравнимо с а по модулю Это обозначение восходит к Гауссу, и мы называем модулями. Множество классов эквивалентности обозначается также через и называется множеством вычетов или целыми числами по модулю т. Следующая теорема перечисляет основные свойства этого отношения эквивалентности и позволяет заключить, что важнейшие алгебраические свойства целых чисел переносятся на целые числа по модулю

Теорема 2.3.7.

(Свойство сокращения.) Если , то , где . В частности, если , то влечет за собой

Доказательство. Мы докажем часть , а остальное предоставим читателю. Из следует, что для некоторого целого числа к. Если то d также делит , откуда вытекает, что Следовательно, для некоторого целого числа к и

Пример. Из равенства мы получаем тогда как из получаем .

Полезная характеризация областей целостности дается следующим правилом сокращения.

Теорема 2.3.8. Нетривиальное коммутативное кольцо D является областью целостности тогда и только тогда, когда из условий следует, что

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

Рассмотрим классы эквивалентности а и b в мы определим сумму и произведение а этих классов через сумму и произведение их представителей. А именно мы имеем сюръективное отображение положим а Из теоремы 2.3.7 вытекает, что это определение корректно, т.е. если — другие представители, то мы получим те же самые классы эквивалентности для суммы и произведения, поскольку Отношение эквивалентности, которое сохраняет алгебраические свойства (такое, как сохраняющее сложение и умножение), называется конгруэнцией.

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

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

Предложение тогда и только тогда, когда

Доказательство. Заметим, что для всякого а выполняется По транзитивности отсюда следует, что то) тогда и только тогда, когда т.е. тогда и только тогда, когда то Но поскольку то делит в точности тогда, когда

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

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

Теорема 2.3.10. Пусть Тогда а имеет мультипликативный обратный по модулю то элемент в том и только том случае, когда

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

Теорема 2.3.11. Для всякого целого числа множество с операциями умножения и сложения по модулю является коммутативным кольцом с единицей и называется кольцом вычетов по модулю Оно является полем тогда и только тогда, когда — простое число.

Доказательство. С помощью определенного ранее сюръективного отображения а также определения сложения и умножения в мы легко можем вывести, что является коммутативным кольцом с единицей, из того, что Z является таким кольцом. Например, для проверки ассоциативности умножения заметим, что для любых а, b и с в Z выполняются соотношения

Пусть теперь m — простое число; тогда все ненулевые элементы в обратимы, и, следовательно, является полем. С другой стороны, если не является простым, то — не поле. Чтобы убедиться в этом, запишем тогда но откуда вытекает, что являются делителями нуля.

Пример. Рассмотрим . Кольцо является полем, так как все его ненулевые элементы 1, 2, 3 и 4 обратимы (обратные элементы — это 1, 3, 2 и 4 соответственно). Кольцо полем не является, поскольку в нем есть делители нуля, например

Отметим попутно, что мультипликативная группа кольца имеет элементов, где — функция Эйлера; другими словами, это группа порядка

Теорема 2.3.12. Характеристика конечного поля — простое число.

Доказательство. Предположим, что характеристика А конечного поля — составное число, т.е. Тогда числа

а отличны от нуля, но что противоречит отсутствию делителей нуля в поле.