Сравнения

Теорема 1.6.1. Пусть m – натуральное число. Для любых целых чисел a и b следующие условия равносильны:

1. a и b имеют одинаковые остатки от деления на m;

2. a – b делится на m, то есть a – b = m × q, для подходящего целого q;

3. a = b + m × q для некоторого целого q.

. Пусть a = m × q ₁ + r, b = m × q ₂ + r, 0 £ r < m, . Тогда a – b = m × q ₁ – m × q ₂ = m × (q ₁ – q ₂) Þ (a – b) m.

2. (a – b) m Þ a – b = m × q, q Î Z, Þ a = b + m × q.

3. Пусть a = b + m × q, a = m × q ₁ + r ₁, b = m × q ₂ + r ₂, 0 £ r ₁, r ₂ < m, . Тогда m × q ₁ + r ₁ = m × q ₂ + r ₂ + m × q Þ r ₁ – r ₂ = m × (q ₂ + q – q ₁) Þ Þ .

Определение 1.6.1. Целые числа а и b называются сравнимыми по модулю m, если они удовлетворяют условиям теоремы 1.6.1. Этот факт обозначают формулой a º b (mod m) или a º b (m). Данное соотношение между целыми числами называют сравнением по модулю m.

Пример 1.6.1. – 6 º 9 º 14 º 24 º 39 º 4 (mod 5). ·

Дата добавления: 2014-01-05