Основные понятия

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

Каждому целому числу отвечает определенный остаток от деления его на m (Глава 1, п.

Сравнимость чисел а и b по модулю m записывается так:

a º b(mod m),

что читается: а сравнимо с b по модулю m.

Теорема 1: Сравнимость чисел а и b по модулю m равносильна:

1. Возможности представить a в виде a = b + mt, где t - целое.

2. Делимости a - b на m.

Доказательство: Из a º b(mod m) следует

a = mq + r, b = mq₁ + r, 0 £ r < m,

откуда

a – b = m(q – q₁), a = b + mt, t = q – q₁.

Обратно, из a = b + mt, представляя b в виде

b = mq₁ + r, 0 £ r < m,

выводим

a = mq + r; q = q₁ + t,

т. e.

a º b(mod m).

Поэтому верно утверждение (1).

Из (1) непосредственно следует утверждение (2). 2