Поле вычетов

Как было показано в разд.1.2.3, полная система вычетов < Z_n,*, + >является коммутативным кольцом.

Исследуем далее мультипликативную полугруппу < Z_n,*>.

Единицей мультипликативной полугруппы является класс 1, поскольку 1* a = a *1=(1 a) mod n = a.

Существуют пары обратных элементов. Например, (n - 1)^-1=(n - 1), поскольку (n -1)*(n -1)=(n ²-2 n +1) mod n =1.

Однако делители нуля не имеют обратных элементов. Действительно, пусть n – составное число и a, b – делители нуля: a * b = b * a =0; a ¹0, b ¹0; и пусть a имеет обратный элемент c: a * c = c * a =1. Тогда b = b *1= b *(a * c)=(b * a)* c =0* c =0, что противоречит предположению b ¹0.

Следовательно, мультипликативная полугруппа < Z_n,*> не образует группу и полная система вычетов не является полем.

Однако, если ввести ограничение, что n – простое число, то мультипликативная полугруппа < Z_n,*> без нуля образует коммутативную (абелеву) группу и полная система вычетов < Z_n,*, + > будет является полем.

Так как операция умножения на множестве Z_n коммутативна, то для доказательства того, что < Z_n,*, + > является полем требуется доказать утверждение: если n – простое число, то для любого a Î{1,2,…, n -1}, (a ¹0), существует b Î{1,2,…, n -1} (b ¹0), такое что a * b = b * a =(ab) mod n =1.

Доказательство. Рассмотрим n -1 чисел a,2 a,3 a,…,(n -1) a, где a Î{1,2,…, n -1}.

Поскольку a < n, a ¹0 и множитель при a тоже меньше n, то произведение двух чисел, которые оба отличны от нуля и меньше простого n, на n не делится. Поэтому все эти числа лежат вне нулевого класса.

Если два числа sa и ta, s, t Î{1,2,…,n-1} лежат в одном классе (sa = in + k, ta = jn + k), тогда их разность sa - ta = a (s - t) должна делится на n (sa - ta = in + k - jn - k = in - jn). Но поскольку оба сомножителя a и (s - t) меньше простого n, это не возможно. Поэтому никакие два числа a,2 a,3 a,…,(n -1) a не лежат в одном классе.

Итак, ни одно из чисел a,2 a,3 a,…,(n -1) a не лежит в классе 0, и все эти числа лежат в разных классах 1,2,3,…, n -1, поэтому в каждом из этих классов лежит ровно одно число из чисел a,2 a,3 a,…,(n -1) a. Значит и в классе 1 лежит некоторое единственное число ba, 1£ b £(n -1). Это значит, что a * b = b * a =(ab) mod n = 1; a, b Î{1,2,…, n -1}, (a ¹0, b ¹0), что и требовалось доказать.

Таким образом, в случае простого n полная система вычетов < Z_n,*, + > является полем.

В этом случае можно ввести операцию деления, кроме деления на нуль

a / b = c, bc mod n = a, b ¹0.

Результаты операций сложения, умножения, вычитания и деления полной системы вычетов < Z ₃,*, + > представлены в табл.1.5 - 1.8 соответственно. Результаты операций сложения, умножения, вычитания и деления полной системы вычетов < Z ₅,*, + > представлены в табл.1.9-1.12 соответственно.