Упражнение 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.