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

Пример

Пусть модуль $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\}$.

Один из методов выполнения арифметических операций над данными целыми числами основан на простых положениях теории чисел. Идея этого метода состоит в том, что целые числа представляются в одной из непозиционных систем – в системе остаточных классов. А именно: вместо операций над целыми числами оперируют с остатками от деления этих чисел на заранее выбранные числа – модули $p_1, p_2, \ldots, p_n$. Чаще всего модули $p_1, p_2, \ldots, p_n$ выбирают из множества простых чисел.