Малый мехмат сравнения по модулю

Малый мехмат сравнения по модулю

Определение. Целые числа a и b называются сравнимыми по модулю m , если они имеют одинаковые остатки при делении на m . То есть a ≡ b (mod m ), если a = q 1 · m + r и b = q 2 · m + r , где 0 ≤ r m , где m — натуральное число, а a , b , q — целые.

Базовое свойство: a ≡ b (mod n ) ⇔ n | ( a − b ).

Если числа n и m имеют одинаковый остаток от деления на k , то их называют сравнимыми по модулю k . Записывается это так: n ≡ m (mod k ). (Если понятно, какой модуль имеется в виду, то скобку для краткости опускают.)

Пример 1. 2 ≡ 7 (mod 5); 11 ≡ 301 (mod 10); 5 ≡ − 4 (mod 9).

Чтобы узнать, сравнимы ли два числа по модулю k , достаточно проверить, делится ли их разность на k .

Сравнение по модулю обладает замечательным свойством, связанным со сложением: если a ≡ b (mod k ) и c ≡ d (mod k ), то a + c ≡ b + d (mod k ). Доказать это просто: раз ( a − b ) и ( c − d ) делятся на k , то и их сумма ( a − b ) + ( c − d ) = ( a + c ) − ( b + d ) делится на k , что и означает, что a + c и b + d имеют одинаковый остаток при делении на k .

Пример 2. 4414 + 14757 ≡ 4 + 2 ≡ 1 (mod 5)
Пример 3. 300 − 151 ≡ 0 − 1 ≡ 2 (mod 3)

Часто помогает такая запись: если a ≡ b (mod k ), то можно записать, что для некоторого целого числа n (возможно, нулевого или отрицательного) a = b + kn . Например, свойство о сложении можно доказать так: a + c = b + kn + d + km = b + d + k ·( n + m ) ≡ b + d (mod k )

Определение 1. Если два числа 1 ) a и b при делении на p дают один и тот же остаток r, то такие числа называются равноостаточными или сравнимыми по модулю p.

Утверждение 1. Пусть p какое нибудь положительное число. Тогда всякое число a всегда и притом единственным способом может быть представлено в виде

a=sp+r, (1)

где s — число, и r одно из чисел 0,1, . p−1.

Читайте также:  Как убавить звук на телефоне панасоник

1 ) В данной статье под словом число будем понимать целое число.

Действительно. Если s получит значение от −∞ до +∞, то числа sp представляют собой совокупность всех чисел, кратных p. Рассмотрим числа между sp и (s+1)p=sp+p. Так как p целое положительное число, то между sp и sp+p находятся числа

Но эти числа можно получить задав r равным 0, 1, 2. p−1. Следовательно sp+r=a получит всевозможные целые значения.

Покажем, что это представление единственно. Предположим, что p можно представить двумя способами a=sp+r и a=s1p+r1. Тогда

(2)

Так как r1 принимает один из чисел 0,1, . p−1, то абсолютное значение r1r меньше p. Но из (2) следует, что r1r кратно p. Следовательно r1=r и s1=s.

Число r называется вычетом числа a по модулю p (другими словами, число r называется остатком от деления числа a на p).

Утверждение 2. Если два числа a и b сравнимы по модулю p, то a−b делится на p.

Действительно. Если два числа a и b сравнимы по модулю p, то они при делении на p имеют один и тот же остаток p. Тогда

где s и s1 некоторые целые числа.

Разность этих чисел

(3)

делится на p, т.к. правая часть уравнения (3) делится на p.

Утверждение 3. Если разность двух чисел делится на p, то эти числа сравнимы по модулю p.

Доказательство. Обозначим через r и r1 остатки от деления a и b на p. Тогда

По утверждению a−b делится на p. Следовательно rr1 тоже делится на p. Но т.к. r и r1 числа 0,1. p−1, то абсолютное значение |rr1| Свойство 1. Для любого a и p всегда

a≡a mod (p).

Свойство 2. Если два числа a и c сравнимы с числом b по модулю p , то a и c сравнимы между собой по тому же модулю, т.е. если

a≡b mod (p), b≡c mod (p).
Читайте также:  Какие процессоры поддерживают ecc память
a≡c mod (p).

Действительно. Из условия свойства 2 следует a−b и b−c делятся на p. Тогда их сумма a−b+(b−c)=a−c также делится на p.

a≡b mod (p) и m≡n mod (p),
a+m≡b+n mod (p) и a−m≡b−n mod (p).

Действительно. Так как a−b и m−n делятся на p, то

(a−b)+ (m−n)=(a+m)−(b+n) ,
(a−b)−(m−n)=(a−m)−(b−n)

также делятся на p.

Это свойство можно распространить на какое угодно число сравнений, имеющих один и тот же модуль.

a≡b mod (p) и m≡n mod (p),
am≡bn mod (p).

Действительно.Так как a−b делится на p, то (a−b)m также делится на p, следовательно

am≡bm mod (p).

Далее m−n делится на p, следовательно b(m−n)=bm−bn также делится на p, значит

bm≡bn mod (p).

Таким образом два числа am и bn сравнимы по модулю с одним и тем же числом bm, следовательно они сравнимы между собой (свойство 2).

a≡b mod (p).
a k ≡b k mod (p).

где k некоторое неотрицательное целое число.

Действительно. Имеем a≡b mod (p). Из свойства 4 следует

a·a≡b·b mod (p).
a·a·a≡b·b·b mod (p).
.
a k ≡b k mod (p).

Все свойства 1-5 представить в следующем утверждении:

Утверждение 4. Пусть f(x1, x2, x3, . ) целая рациональная функция с целыми коэффициентами и пусть

a1b1, a2b2, a3b3, . mod (p).
f(a1, a2, a3, . )≡f(b1, b2, b3, . ) mod (p).

При делении все обстоит иначе. Из сравнения

am≡bm mod (p)

не всегда следует сравнение

a≡b mod (p).

Утверждение 5. Пусть

am≡bm mod (p),
a≡b mod (p/λ),

Доказательство. Пусть λ наибольший общий делитель чисел m и p. Тогда

m=m1λ и k=k1λ.

Так как m(a−b) делится на k, то

имеет нулевой остаток. Тогда

.

имеет нулевой остаток, т.е. m1(a−b) делится на k1. Но числа m1 и k1 числа взаимно простые. Следовательно a−b делится на k1=k/λ и, тогда, a≡b mod (p/λ).

Читайте также:  Как убрать вратаря в нхл

Утверждение 6. Если

a≡b mod (p)

и m является один из делителей числа p, то

a≡b mod (m).

Действительно. a−b делится на p. p делится на m. Следовательно a−b делится на m.

Утверждение 7. Если

a≡b mod (p), a≡b mod (q), a≡b mod (s)
a≡b mod (h),

где h наименьшее общее кратное чисел p,q,s.

Действительно. Разность a≡b должна быть числом, кратным p,q,s. и, следовательно должна быть кратным h.

В частном случае, если модули p,q,s взаимно простые числа, то

a≡b mod (h),

Заметим, что можно допустить сравнения по отрицательным модулям, т.е. сравнение a≡b mod (p) означает и в этом случае, что разность a−b делится на p. Все свойства сравнений остаются в силе и для отрицательных модулей.

Ссылка на основную публикацию
Люстра с пультом управления светодиодная инструкция
Идея установить и подключить люстру с пультом замечательна тем, что хозяева квартиры получают возможность управлять освещением, не привязываясь к выключателю....
Линза для лазерного диода
Асферические линзы используются для коррекции сферических аберраций. Вместо применения сложных линз такие аберрации могут быть снижены до минимума при использовании...
Линукс для нетбука acer aspire one
Автор — Андрес Брачо (Andrés Bracho) Я не технарь, не компьютерщик и не программист. Я всего лишь среднестатис-тический пользователь, кото-рый...
Ля рош позе скидки
12 актуальных предложений март 2020 Сэкономьте 10% с промокодом при покупке более 3000 рублей Приобретите в интернет-магазине La Roche Posay...
Adblock detector