Теорема о делении с остатком. Алгоритм Евклида — различия между версиями
Isaeva (обсуждение | вклад) |
Isaeva (обсуждение | вклад) |
||
| Строка 26: | Строка 26: | ||
Легко доказывается, что для любых целых чисел <math>a</math> и <math>b</math>, <math>b \not= 0</math> деление с остатком возможно и числа <math>q</math> и <math>r</math> определяются однозначно. В нашем примере полная система наименьших неотрицательных вычетов есть множество <math>\left\{0, 1, 2, 3, 4, 5 \right\}</math>; полная система наименьших положительных вычетов – множество <math>\left\{0, 1, 2, 3, 4, 5, 6 \right\}</math>; полная система наименьших по абсолютной величине вычетов – множество <math>\left\{-2,-1, 0, 1, 2, 3 \right\}</math>; приведённая система вычетов – множество <math>\left\{1,5 \right\}</math>, так как <math>\phi(6) = 6\,\left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right) = 2</math> ; фактор-множество <math>Z/{\equiv}_6 = \left\{K_0, K_1, K_2, K_3, K_4, K_5 \right\}</math>. | Легко доказывается, что для любых целых чисел <math>a</math> и <math>b</math>, <math>b \not= 0</math> деление с остатком возможно и числа <math>q</math> и <math>r</math> определяются однозначно. В нашем примере полная система наименьших неотрицательных вычетов есть множество <math>\left\{0, 1, 2, 3, 4, 5 \right\}</math>; полная система наименьших положительных вычетов – множество <math>\left\{0, 1, 2, 3, 4, 5, 6 \right\}</math>; полная система наименьших по абсолютной величине вычетов – множество <math>\left\{-2,-1, 0, 1, 2, 3 \right\}</math>; приведённая система вычетов – множество <math>\left\{1,5 \right\}</math>, так как <math>\phi(6) = 6\,\left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right) = 2</math> ; фактор-множество <math>Z/{\equiv}_6 = \left\{K_0, K_1, K_2, K_3, K_4, K_5 \right\}</math>. | ||
| + | |||
| + | Один из методов выполнения арифметических операций над данными целыми числами основан на простых положениях теории чисел. Идея этого метода состоит в том, что целые числа представляются в одной из непозиционных систем – в системе остаточных классов. А именно: вместо операций над целыми числами оперируют с остатками от деления этих чисел на заранее выбранные числа – модули <math>p_1, p_2, \ldots, p_n</math>. | ||
| + | Чаще всего модули <math>p_1, p_2, \ldots, p_n</math> выбирают из множества простых чисел. | ||
Версия 10:11, 10 декабря 2014
Пример
Пусть модуль 
.
Тогда имеем шесть классов разбиения множества целых чисел по модулю 6:
;
;
;
;
;
,
где через 
обозначен остаток от деления целого числа на 6.
Напомним теорему о делении с остатком:
Теорема о делении с остатком
Для любых целых 
и 
, 
, существует единственный набор целых чисел 
и , что 
и 
, где 
— модуль числа .
Легко доказывается, что для любых целых чисел и , деление с остатком возможно и числа и определяются однозначно. В нашем примере полная система наименьших неотрицательных вычетов есть множество 
; полная система наименьших положительных вычетов – множество 
; полная система наименьших по абсолютной величине вычетов – множество 
; приведённая система вычетов – множество 
, так как 
; фактор-множество 
.
Один из методов выполнения арифметических операций над данными целыми числами основан на простых положениях теории чисел. Идея этого метода состоит в том, что целые числа представляются в одной из непозиционных систем – в системе остаточных классов. А именно: вместо операций над целыми числами оперируют с остатками от деления этих чисел на заранее выбранные числа – модули 
.
Чаще всего модули выбирают из множества простых чисел.
