5Конечные арифметики

5.1Деление с остатком.

Рассмотрим сначала натуральные числа. Пусть нам надо разделить, например,17 на 3.

Мы берём , скажем, 17 пуговиц и начинаем укладывать их рядами по три в ряд:

П олучилось пять рядов и осталось ещё две пуговицы. Мы этот факт описываем равенством 17=35+2, в котором 17 называется делимым, 3 – делителем, а 2 – остатком. Нас будут интересовать, главным образом, остатки. Во-первых, этот остаток не может превысить и даже равняться делителю – иначе мы могли бы из них ещё один ряд составить и добавить к выложенным прямоугольником пуговицам. Во-вторых, он больше или равен нулю. Если он оказался равен нулю, то мы говорим, что делимое делится на делитель без остатка, или ещё, по-другому, нацело. Так, нацело делятся 22 на 2, 28 на 7 и т.д. Теперь мы возьмём это свойство остатка за основу и дадим такое определение. Пусть нам даны два целых числа, уже теперь не обязательно натуральные, a и b. Рассмотрим уравнение a=bX+Y⁹.

На Y наложим ограничение: он должен быть меньше b и не меньше нуля: 0Y<b.

Оказывается, что этим условием оба целых числа Х и Y определяются однозначно.

Упражнение 31.

a) Решите (в целых числах) уравнение -1=4X+Y;

b) Разделите с остатком -8 на 3.

c) Заполните таблицу и нанесите полученные значения на целочисленную координатную декартову плоскость:

Х	-8	-7	-6	-5	-4	-3	-2	-1	0	1	2	3	4	5	6	7	8
Y=Остаток от деления Х на 4

Мы видим, что графиком этой функции является «пила» - через четыре деления значения функции повторяются (такие функции называются периодическими). Если провести параллельные оси 0Х прямые на высоте 1, 2,или 3 то их точки пересечения с графиком будут расположены на расстоянии 4 друг от друга. Теперь объясним, почему в уравнении a=bX+Y

оба целых числа Х и Y определяются однозначно. Рассмотри для примера b=5. Отметим на прямой все числа кратные 5:

Тогда число а попадёт на один из отрезков (длиной в 4 деления), на которые числа, кратные пяти разбивают целочисленную прямую. Расстояние (число делений) от а до ближайшего кратного пяти числа (до левой границы отрезка) не превышает общей длины отрезка минус 1, потому, что если а попадёт на правую границу, то оно само кратно 5 и тогда с=0. Левая граница – тоже кратное 5 число и поэтому имеет вид 5b при некотором b. Таким образом, 5Х – это наибольшее кратное 5, не превосходящее а (или само а, или ближайшее к нему слева от него).

Формальное доказательство описывает эти факт: то, что вся прямая разбивается на непересекающиеся участки по пять чисел в каждом. Вот оно:

пусть a=bX+Y и в то же время a=bZ+W. Тогда вычтем из первого равенства второе и получим

0=bX+Y-bZ-W. Отсюда b(X-Z)=W-Y. Если W-Y <0, то умножим это равенство на -1:

b(X-Z)=Y-W. Слева у нас стоит число, кратное b, а справа число меньше, чем b (так как 0Y<b, 0W<b и 0Y-W). Этого, разумеется, не может быть, если только W-Y0 – среди чисел 0, 1, 2, …,b-1 только 0 делится на b. Но Но W-Y=0 означает, что W=Z и тогда b(X-Z)=0, а, значит, и X-Z=0 , т.е. и X=Z.

Введём теперь на Z бинарное отношение R: аb, если оба дают один и тот же остаток при делении на 5. Записывают это так: ab(mod5). Читают эту запись так: «а сравнимо с b по модулю пяти». Конечно, пятёрка служит только для иллюстрации, её можно заменить любым другим целым числом.

Упражнение 32.

а) Докажите, что отношение R -это отношение эквивалентности.

б) Докажите, что ab(modс)a-b0(modc)

Итак, все числа разбиваются этим отношением на классы: класс нуля – все числа, делящиеся нацело на с, класс единицы – дающие 1 в остатке, и т.д. Будем обозначать эти классы чертой сверху над их представителями:

Введём теперь операции – сложения и умножения в множестве классов (для определённости – снова по модулю 5). Как всегда, сделаем это с помощью представителей.

Пусть а – представитель класса (по модулю с), b– представитель класса . Тогда сумма элементов a и b – тоже представитель какого-то класса. Этот класс мы обозначим, как и назовём суммой классов и .

Аналогично произведение классов определяется как класс произведения представителей:  = . В правой части равенства мы сначала умножаем представителей классов (то есть, числа), а затем находим класс, в котором находится произведение (то есть, делим на с и находим остаток).

Замечание.

Умножение классов (слева от знака равенства, определяющего это умножение) тоже надо было бы обозначать каким-то иным символом, чтобы не спутать его с умножением чисел, но мы оставим его таким же, чтобы не перегружать записи значками в надежде, что вы будете иметь это ввиду и не перепутаете.

Пример.

Рассмотрим все чётные числа – кратные двум. Все они получаются по формуле m=2n. Подставляя вместо n всевозможные целые числа, получим все чётные числа. Вот кусочек этой бесконечной таблицы:

n	…	-2	-1	0	1	2	3	4	…
m=2n	…	-4	-2	0	2	4	6	8	…

Другой класс чисел по модулю двух – это нечётные числа. Они получаются по формуле m=2n+1 (можно было бы использовать также и 2n-1, 2n+3 и т.д.)

n	…	-2	-1	0	1	2	3	4	…
M=2n+1	…	-3	-1	10	3	5	7	9	…

Итак, в случае деления на 2 мы имеем два класса - и .

Посмотрим, как они ведут себя при сложении и умножении: 2p+2k=2(p+k) + = ; 2p+(2k+1)=2(p+k)+1 + = ; (2p+1)+(2k+1)=2(p+k)+1+1=2(p+k+1) + = .

2p2k=2(p2k)  = ; 2p(2k+1)=2(p(2k+1))  = ; (2p+1)(2k+1)=2p(2k+1)+2k+1=2[p(2k+1)+k]+1   = .

Итак, таблицы сложения и умножения по модулю двух выглядят так:

+



Упражнение 33.

Составьте таблицы сложения и умножения по модулю трёх.

Упражнение 34.

Докажите, что определения операций сложения и умножения modc (по модулю числа с) не зависят от выбора представителей (т.е., проверьте их корректность).

Применяя определение умножения для двух одинаковых классов, получим правило возведения в степень: ⁿ= . Применим это правило, для определения, например, 7¹⁰⁰(mod10).

7¹=7º7mod10;

7²=49º9mod10º-1mod10;

7⁴=7²7²º(-1)mod10 ´(-1)mod10=1mod10;

7⁵=7⁴´7º1mod10´7mod10=7mod10.

Мы видим, что результаты начинают повторяться. Длина цикла или периода повторения в данном примере – 4: через каждые 4 шага мы получаем прежний ответ; каждый пятый класс – тот же самый. Итак, 4-ый, 8-ой, 12-ый,…,100-ый результат будет 1. Ответ: 7¹⁰⁰º 1(mod10).

Упражнение 35.

Вычислите (5²⁰⁰+8³⁰⁰)mod11

Арифметика классов, которую мы построили, называется конечной арифметикой, так как, в отличие от целых чисел, которых бесконечно много, различных классов (как и остатков от деления на число с) конечное число (а именно, с).

Научимся теперь находить числа по их остаткам от деления на заданные числа. Рассмотрим модельную задачу: в столовую привезли гору мандаринов из Абхазии.

Если раздавать каждому ученику по 5 мандаринов, то останутся два мандарина, если раздавать по 6 мандаринов, то останутся 4 мандарина, если раздавать по 7 мандаринов, то останется один мандарин, если раздавать по 8 мандаринов, то останется 6 мандаринов. Сколько учеников учится в этой школе?

Как обычно, обозначим неизвестное число учеников буквой х и составим систему уравнений: как обычно, начнём из одного уравнения подставлять х в другое. Начнём с последнего (как наибольшего делителя – 8): Х=8k+6, k=0,1,2,…и подставим в предпоследнее (поднимаемся снизу вверх): (8k+6)mod71;

8k(mod7)+6mod71; 8mod7kmod7+6mod7º1; kmod7+6mod7º1; добавим по 1; к обеим частям равенства: kmod7 º2.Этому уравнению удовлетворяет, например, число k=2. Итак, мы нашли первый Х удовлетворяющий обоим уравнениям – последнему и предпоследнему: Х=82+6=22. Последующие числа, удовлетворяющие этим двум уравнениям, будут идти с периодом 78=56: Х=22+56m. Подставим теперь это выражение для Х во второе уравнение: (22+56m) mod6º4;

22 mod6+(56 mod6)(m mod6) º4; 4mod6+2m(mod6)º4; 2mº0 (mod6) m=0. Итак, первым числом, удовлетворяющим последним трём уравнением будет по-прежнему 22. Только последующие будут идти теперь уже с периодом 786=336; Х=22+336n. Подставляем найденное выражение для Х в первое уравнение: (22+336n) mod5º2;

2 mod5+1n mod5º2; (n+2) mod5º2; n=0. Итак, число 22 удовлетворяет всем четырём условиям задачи. Но вряд ли правдоподобно выглядит такое маленькая школа, разве что малокомплектная в сельской местности. Следующим числом, удовлетворяющим этим условиям, будет 22+336×5=1702 ученика. Средняя по размерам американская High School.

Упражнение 36.

Найдите решение системы при условии, что Х<1600