Статья по алгебре на тему "Сравнение по модулю. Арифметрика остатков""

Сравнение по модулю. Арифметика остатков

Учитель математики

ОБОУ ЦДО «Новые технологии»

Носикова О.В.

Боги открыли людям не все. В поиск пустившись,

люди сами открыли немало.

Ксенофан

            Число а делится на в, если при делении а на в получается целое число с.

            Поделить с остатком целое число а на натуральное число в, это значит найти такие целые числа k и r, для которых выполняется равенство a=kb+r, при этом  r не отрицательно и меньше b. k— неполное частное, r- остаток.

            Например, нужно найти остаток от деления 100 на 7.

100 = 14х7+2, где 14 — неполное частное, 2 — остаток.

            Рассмотрим случай, когда нужно найти остаток при делении отрицательного числа. Кажется, что -100 = -14х7+(-2). Но остаток не может быть отрицательным. В этом случае нужно найти ближайшее число к -100, которое делится на 7, но которое его не превосходит. То есть 7 нужно умножить не на -14, а на -15.

-100=-15х7+5

            Для любого целого числа а и любого натурального числа в существует единственная пара чисел  k и r, при которых выполняется равенство  a=kb+r, при этом  r не отрицательно  и меньше b.

(mod m) - а сравнимо с в по модулю m означает, что а и в имеют одинаковые остатки при делении на m.

            Например (mod 7) - 16 сравнимо с -12 по модулю 7.

16=2х7+2

-12=-2х7+2

            Для того, чтобы понять, что числа имеют одинаковые остатки, достаточно убедиться, что они отличаются друг от друга на целое число делителей.

            Докажем следующее утверждение: а сравнимо с в по модулю m тогда и только тогда, когда разность этих чисел а-в делится на m.

            Доказательство.

Первая часть доказательства.

Если мы знаем, что у чисел одинаковые остатки, то

a=km+r

b=lm+r

a-b=km+r-lm-r=(k-l)m. Доказали — а-в это сколько-то раз по m.

Вторая часть доказательства.

Пусть мы знаем, что а-в делится на m. Предположим, что у а и в разные остатки.

a=km+r₁

b=lm+r₂

Но мы знаем, что а-в делится на m, значит a-b==(k-l)m + (r₁ — r₂). Но если а-в делится на m, первое слагаемое делится на m, тогда и второе слагаемое r₁ — r₂  должно делиться на m. Но что такое  r₁ — r₂ ? Это остатки, каждый из которых лежит в интервале от 0 до m-1. Их разность будет лежать в интервале от -(m-1) ….(m-1). Но среди этих чисел есть только одно число, которое делится на m —  это 0. Значит r₁ — r₂ =0. Значит r₁ = r₂.

Наше утверждение доказано.

            Докажем несколько свойств сравнения по модулю.

1.      Если а сравнимо с в по модулю m и с сравнимо с d по модулю m, то сумма а+с сравнима с суммой в+d по модулю m.

Доказательство.

(а+с)- (в+d)= (а-в)+(с-d). Раз (а-в) делится на m и (с-d) делится на m, то и их сумма делится на т, а значит разность а+с и в+d  делится на т и они имеют одинаковые остатки.

2.      Если а сравнимо с в по модулю m и с сравнимо с d по модулю m, то разность а-с сравнима с разностью в-d по модулю m.

Доказательство.

(а-с)- (в-d)= (а-в)-(с-d). Раз (а-в) делится на m и (с-d) делится на m, то и их разность делится на т, а значит а-с и в-d имеют одинаковые остатки.

3.      Если а сравнимо с в по модулю m и с сравнимо с d по модулю m, то произведение а*с сравнимо с произведением в*d по модулю m.

ас-bd=(прибавим и вычтем вс)=ас-bс+bc-bd=c(a-b)+b(c-d).Это выражение делится на т, значит и произведение делится на т.

4.      Если у чисел одинаковые остатки, то и у их равных степеней тоже одинаковые остатки. Доказательство следует из свойства 3.

Рассмотрим пример.

            Найдем остаток при делении 2²⁰¹⁸ на 15. Какая степень 2 не очень сильно отличается от числа, которое делится на 15? Это 2⁴, 2⁴=16. А какой остаток у 16 при делении на 15? 1. То есть 16 сравнимо с 1 по модулю 15. Значит 16^к сравнимо с 1к по модулю 15.

2²⁰¹⁸=2²*2²⁰¹⁶=4*16⁵⁰⁴. Но 16 в любой степени сравнимо в 1 по модулю 15, значит с точки зрения делимости на 15  4*16⁵⁰⁴ это тоже самое, что 4*1 = 4. Значит у числа 2²⁰¹⁸ такой же остаток при делении на 15, как и у числа 4. Этот остаток равен 4.

Источники:

Сравнение по модулю. Арифметика остатков. Борис Трушин https://www.youtube.com/watch?v=lHgMi8b27A4&t=4s

Понятие делимости и ее свойства. https://100urokov.ru/predmety/urok-2-delimost