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

Пример

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

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

$K_0 = {\ldots,-18,-12,-6,0,6,12,18,\ldots}, r=0$;

$K_1 = {\ldots,-17,-11,-5,1,7,13,19,\ldots}, r=1$;

$K_2 = {\ldots,-16,-10,-4,2,8,14,20,\ldots}, r=2$;

$K_3 = {\ldots,-15,-9,-3,3,9,15,21,\ldots}, r=3$;

$K_4 = {\ldots,-14,-8,-2,4,10,16,22,\ldots}, r=4$;

$K_5 = {\ldots,-13,-7,-1,5,11,17,23,\ldots}, r=5$,

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