Дискретная математика. Множества. Отображения. Отношения

49 отношение называется отношением равенства по модулю пять и обо - значается символом (mod5) m n ≡ или (mod5) m n ≡ . Очевидно , что 5 5 ( ) ( ) r m r n = ↔ число m n − делится без ос - татка на пять , т . е . возможно представление 5 m n k = + , при некото - ром значении k ∈ Z . Это значит , что равны по модулю пять все числа , отличающиеся друг от друга на число , кратное пяти . Так , 1 6 11 (mod5) ≡ ≡ , 2 7 12 (mod5) ≡ ≡ , 3 8 (mod5) ≡ и т . д . Аналогично можно определить равенство по произвольному модулю p ∈ N . При 1 p = получаем тривиальное равенство : все числа равны по этому модулю . Отношение равенства по модулю 1 p ≠ на множестве целых чисел Z определяется следующим образом : ( ) , (mod ) ( ) m n m n p k m n pk ∀ ∈ ≡ ↔ ∃ ∈ = + Z Z . (5.8) Равенства по модулю называются сравнениями . Свойства сравнений Сравнения обладают многими свойствами обычных равенств : , , , , , , , ( 0) m n k p r l s p ∀ ∈ > Z (mod ) m m p ≡ ; (5.9) (mod ) (mod ) m n p n m p ≡ → ≡ ; (5.10) (mod ) & (mod ) (mod ) m n p n k p m k p ≡ ≡ → ≡ . (5.11) • Сравнения по одному модулю можно почленно складывать и перемножать : ( (mod ) & (mod )) m n p k r p ≡ ≡ → ( (mod )) & ( (mod )) m k n r p mk n r p → ± ≡ ± ≡ . (5.12)