6.4. Кольцо классов вычетов.

Пусть Z - множество целых чисел, и m  Z. Введем на Z бинарное отношение  следующим образом: для a, b Z пусть по определению ab  a – b=km при некотором k Z. При m  0 это означает, что ab  m |(a – b).

Утверждение.  - отношение эквивалентности на Z.

Доказательство.

 - рефлексивно, так как  аZ a – a = 0m  a  a.

 - симметрично, так как если a  b, то a – b = km, k Z 

b – a =(-k)m, и -k Z  b a.

 - транзитивно, так как если a  b, и b с, то a – b = km, где k Z, b – c = lm, где l Z  (a – b) +(b – c) = a – c = (k+l)m, и k+l Z  a  с.



Классы эквивалентных элементов по отношению  мы будем обозначать cl_ a или (если ясно, какое  имеется ввиду) cl a или . Очевидно, cl_ a = {b Z | b a } =

= { b Z | b – a = km для некоторого k Z }=

= { b Z | b – a  mZ} = { b Z | b  a + mZ} = a + mZ.

Так как  - отношение эквивалентности на Z, то Z разбива­ется на непересекающиеся классы эквивалентных элементов.

Фактормножество Z/, то есть множество классов эквива­лентных элементов, мы будем обозначать Z_m или Z/(m).

Если b cl a, то говорят, что b – представитель из cl a.

Очевидно, при m = 0  a cl a = a, а отношение эквивалентности – это отношение равенства. Таким образом, при m = 0 Z_m =Z.

Далее будем считать, что m  0.

Если a  b, то часто пишут a b(mod m) или a b(m), и говорят, что a и b сравнимы по модулю m. А классы эквива­лентных элементов называют классами вычетов по модулю m или классами по модулю m.

Разделим a и b на m с остатком. Пусть a = mq₁ + r₁,

b = mq₂ + r₂ , где 0  r₁ m, 0  r₂ m. Очевидно, a - r₁= mq₁,

то есть m|(a – r₁)  =. Аналогично, =.

Утверждение. = r₁= r₂ .

Доказательство. . Пусть r₁= r₂ . Тогда ===.

. Пусть =,и r₁  r₂, например, r₁ r₂. Тогда ===

 r₁ r₂  m| (r₁ - r₂). Но 0  r₁ - r₂  m. Получили противо­речие, то есть r₁= r₂.



Из утверждения мы получаем, что различных классов по модулю m ровно столько, сколько существует различных ос­татков от деления на m, то есть существует m различных классов, и Z_m = {,,,…,}.

Очевидно, =,=,=,=.

Зададим на Z_m структуру кольца.

1. Определим операции сложения и умножения так:

пусть +=,=.

Докажем корректность нашего определения, то есть неза­висимость его от выбора представителей в классах.

Пусть a₁,b₁, то есть =,=. Тогда

a₁= a + km, b₁= b + lm, и a₁+ b₁= a + b + (k + l)m,

a₁ b₁= ab +(kb + al + klm)m  (a₁+ b₁) (a + b), (a₁ b₁)(a b)  =, =. Корректность доказана.

2. Проверим свойства операций.

1. (+)+=+===+=

=+(+) – это свойство ассоциативности сложения в Z_m следует из ассоциативности сложения в Z.

2. Так как   Z_m +=, то в Z_m  нейтральный

элемент по сложению.

3. Так как   Z_m +=, то   Z_m  проти­воположный элемент по сложению: - =.

Свойства 4, 5, 8, 9 из определения кольца следуют из соот­ветствующих свойств кольца целых чисел и доказываются так же, как и свойство 1.

Упражнение. Доказать свойства 4, 5, 8, 9.

6. Так как   Z_m =, то в Z_m  нейтральный

элемент по умножению.

Таким образом, мы доказали, что Z_m - АКУ-кольцо.

Пример. Выпишем таблицы сложения и умножения для Z₆.

Таблица сложения

Таблица умножения

+

х

Так как =, то и в Z₆ являются делителями нуля. В то же время =, то есть - обратимый элемент в Z₆ .

Утверждение. Элемент  Z_m обратим  НОД(a,m)= 1.

Доказательство.

. Пусть   Z_m такой, что = (ab) 1 ab = 1 + km

 ab - km = 1, и если d|a, d|m, то d|1.

. Пусть НОД(a,m) = 1. Тогда  , Z_m ,  , также  . В самом деле, если =,то = (ac)(ad)  m|(ac - ad)  m|a(c - d). Но НОД(a,m) = 1

m|(c - d)  c d  =- противоречие. Таким образом, все

элементы из Z_m различны  Z_m = Z_m    Z_m

та­кой, что =.



Следствие. Z_m – поле  m – простое число.

Доказательство. . Если m = p – простое число, то

 a  {1,2, …, p - 1} НОД(a,p)= 1  - обратим, Z_m – поле.

. Пусть Z_m – поле, и m – непростое число, m = kl, где k  1, l  1. Тогда НОД(k, m)  1, и для элемента  Z_m ,  ,об­ратный элемент в Z_m не существует - противоречие. Значит, m – простое.

