Бинарная операция – модуль.

Пусть даны два действительных числа m и n. Частным от деления n на m называется величина – , а остатком от деления n на m называется выражение «n mod m». Тогда для любых действительных чисел n и m:

n = m + n mod m.

Определение. Для произвольных действительных чисел x и y определим бинарную операцию – модуль y:

x mod y = x – y , если y ≠ 0. (11.1)

(Модулем называют число, которое стоит после «mod»)

Пример 1: 7 mod 4 = 7 – 4 = 3,

7 mod - 4 = 7 – (– 4) = – 1,

– 7 mod 4 = – 7 – 4 = 1,

– 6 mod – 4 = – 6 – (– 4) = – 2.

В случае когда x и y – вещественные положительные числа, смысл

x mod y легко уловить интуитивно.

Например, представим себе секундную стрелку часов, которая движется по кругу с длиной окружности 60, точкам которой приписаны вещественные числа из интервала [0, 60). Когда стрелка пробежит расстояние х по окружности, она остановится в точке x mod 60. А пока стрелка движется по кругу, точка 0 встретится на ее пути раз.

В случае когда x и y – вещественные отрицательные числа, нужно внимательно осмыслить определение, чтобы выяснить, что представляет собой x mod y. Разберем случай, когда y < 0:

7 mod - 4=7 – (– 4) = –1.

Величина = = – 2, т.к. пол числа х – есть наибольшее целое, меньшее или равное х.

Из рассмотренных примеров и определения функции пол можно заключить, что величина x mod y лежит между нулем и модулем:

0 ≤ x mod y < y при y > 0

0 ≥ x mod y > y при y < 0.

В случае если y = 0, то x mod 0 = x. Это значит, что x mod y отличается от х на величину кратную у. Иными словами x mod 0 = x

тогда и только тогда, когда х кратно у. Подобное соглашение сохраняет свойство x mod y всегда отличаться от х на величину, кратную у.

Как говорилось выше, любое действительное число можно представить в виду суммы его целой и дробной частей: х = + {x}. Дробная часть числа может быть представлена как x mod 1, потому что

х = + x mod 1.

Пример 2: Пу сть х = 2, 5. Тогда 2, 5 = + 2, 5 mod 1. Найдем целую и дробную части числа 2, 5:

= 2;

2, 5 mod 1 = 2, 5 – 1· = 2, 5 – 1 · 2 = 0, 5.

Итак, 2, 5 = 2 + 0, 5.

Свойство 1: Операция mod подчиняется распределительному закону:

с(х mod y) = (сх) mod (сy), где с, х, у Î R.

∆ Действительно,

с(х mod y) = с(x – y ) = сх – су = (сх) mod (сy) = сх mod сy.

В примере 1 иллюстрируется этот закон для случая с = – 1. ▲

Свойство 2: Если для любых действительных чисел х, у и целого числа z

х mod z = y mod z, то х – у — целое число, кратное z.

∆ Доказательство. Для доказательства используем определение операции модуль: x mod z = x – z ; y mod z = y – z .

Тогда, x = x mod z + z ; y = y mod z + z . Составим разность: x – y = x mod z + z – y mod z – z .

Т. к. по условию х mod z = y mod z, то

x – y = z – z = z ( – ).

Разность полов, стоящая в скобках есть целое число, а, следовательно, и вся правая часть есть целое число, кратное z. ▲

Определение. Если два целых числа х и у удовлетворяют условия:

х mod z = y mod z, то говорят, что «х сравнимо с у по модулю z» и записывают: х ≡ у (по модулю z).

Исходя из вышедоказанного свойства, можно сказать, что х и у сравнимы по модулю z, если z делит разность х – у: х ≡ у (по модулю z).

Определение. Два целых числа х и у называются взаимно простыми, если их наибольший общий делитель равен 1, т.е. числа х и у не имеют общих множителей. Символически записывают: х ^ у.

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

Свойство 3: Если s ≡ t (mod z) и х ≡ у (mod z), то справедливы следующие утверждения: a) s + x ≡ t + y (mod z); b) s – x ≡ t – y (mod z) и

c) s x ≡ t y (mod z).

∆ Доказательство. Рассмотрим сначала равенства а) и b). Из определения сравнимости чисел s, t и x, y можем записать: z/(s – t) и z/(x – y). Следовательно, z/(s – t) ± z/(x – y), откуда сделав некоторые преобразования, получим: z/(s + x) – z/(t + y) и z/(s – x) – z/(t – y), что по определению соответствует утверждениям а) и b).

Рассмотрим теперь равенство с). Из свойства 2 следует, что разности

s – t и x – y принадлежат множеству целых чисел и кратны числу z, т.е.

s – t Î z Z; x – yÎ z Z. Тогда sx – ty = (sx – tx) + (tx – ty)=(s – t)x–t(x – y) Î zZ, т.е. s x = t y (mod z). ▲

Свойство 4: Если числа kх и kу сравнимы по модулю z, где k их общий множитель — kх ≡ kу (mod z), то обе части сравнения можно разделить на число k, взаимно простое с z.

Доказательство. Из определения kх ≡ kу (mod z) следует, что z делит разность kx – ky, т.е. z / k(x – y). Числа z и k взаимно простые по условию, следовательно, z делит разность (x – y). Тогда по определению числа x и y сравнимы по модулю z: х ≡ у (mod z). ▲

Свойство 5: Если в сравнении kх ≡ kу (mod kz), (где k ≠ 0) x, y и модуль z имеют общий множитель k, то каждое из этих чисел можно разделить на k.

Доказательство. Для доказательства воспользуемся определением модуля. Т.К. kх ≡ kу (mod kz), то kz / k(x – y), следовательно, z / (x – y), а это значит х ≡ у (mod z). ▲

Свойство 6: Если числа s и t взаимно простые, т.е. s ^ t, то x сравнимо с y по модулю st х ≡ у (mod st) тогда и только тогда, когда

х ≡ у (mod s) и х ≡ у (mod t)

Доказательств. Пусть х ≡ у (mod s) и х ≡ у (mod t), то можем записать: s / (x – y) и t / (x – y), причем x и y – произвольные целые числа,

x ≠ y. Тогда разность x – y делится на s и на t, где числа s и t взаимно простые, s ^ t. Тогда x – y делится на st.

Обратное, если х ≡ у (mod st), то s t / (x – y).

Следовательно, s / (x – y) и t / (x – y), т.е. х ≡ у (mod s) и х ≡ у (mod t), для любых х и у.