Теорема о делении с остатком. Алгоритм Евклида

Материал из Модулярная арифметики
Перейти к: навигация, поиск

Пример

Пусть модуль p = 6.

Тогда имеем шесть классов разбиения множества целых чисел по модулю 6:

K_0 = \left\{\ldots,-18,-12,-6,0,6,12,18,\ldots \right\}, r=0;
K_1 = \left\{\ldots,-17,-11,-5,1,7,13,19,\ldots \right\}, r=1;
K_2 = \left\{\ldots,-16,-10,-4,2,8,14,20,\ldots \right\}, r=2;
K_3 = \left\{\ldots,-15,-9,-3,3,9,15,21,\ldots \right\}, r=3;
K_4 = \left\{\ldots,-14,-8,-2,4,10,16,22,\ldots \right\}, r=4;
K_5 = \left\{\ldots,-13,-7,-1,5,11,17,23,\ldots \right\}, r=5,

где через r обозначен остаток от деления целого числа на 6.

Напомним теорему о делении с остатком:

Теорема о делении с остатком

Для любых целых a и b, b \not= 0, существует единственный набор целых чисел q и r, что a = bq + r и 0 \le r < |b|, где |b| — модуль числа b.

Легко доказывается, что для любых целых чисел a и b, b \not= 0 деление с остатком возможно и числа q и r определяются однозначно. В нашем примере полная система наименьших неотрицательных вычетов есть множество \left\{0, 1, 2, 3, 4, 5 \right\}; полная система наименьших положительных вычетов – множество \left\{0, 1, 2, 3, 4, 5, 6 \right\}; полная система наименьших по абсолютной величине вычетов – множество \left\{-2,-1, 0, 1, 2, 3 \right\}; приведённая система вычетов – множество \left\{1,5 \right\}, так как \phi(6) = 6\,\left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right) = 2 ; фактор-множество Z/{\equiv}_6 = \left\{K_0, K_1, K_2, K_3, K_4, K_5 \right\}.