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

51 если числа k и p – взаимно просты . ( Числа называются взаимно простыми , если не имеют общих делителей кроме единицы ). На - пример , 30 42 (mod2) 10 14 (mod2) ≡ → ≡ . Здесь 3, 2 k p = = . Заметим , что если k и p не являются взаимно простыми , то сокращение невозможно . Например , ( ) 28 16 mod12 ≡ , но 7 4 ≡/ ( ) mod12 . Здесь 4; 12 k p = = . Эти числа не являются взаимно про - стыми и поэтому деление сравнения ( ) 28 16 mod12 ≡ на число 4 k = невозможно . • В сравнении ( ) mod m n p ≡ все три числа m , n , p можно умножить на одно и то же целое положительное число и разделить на любой их общий положительный делитель : 0 k ∀ > ( ) ( ) mod mod m n p km kn kp ≡ ↔ ≡ ; (5.19) • Если равенство справедливо по нескольким модулям , то оно справедливо и по модулю , равному общему наименьшему кратному этих модулей : ( ) ( ) 1 (mod ) &... & mod mod k m n p m n p m n r ≡ ≡ → ≡ , (5.20) где ( ) 1 2 , , ..., k r HOK p p p ≡ – наименьшее общее кратное модулей 1 2 , , ..., k p p p . Например , ( ) ( ) ( ) 16 22 mod3 &16 22 mod2 16 22 mod6 ≡ ≡ → ≡ . Здесь 1 3 p = , 2 2 p = , ( ) 3, 2 6 r HOK = = . • Если 0 k > – делитель модуля p , то ( ) ( ) mod mod m n p m n k ≡ → ≡ . (5.21) Например , ( ) ( ) 35 20 mod15 35 20 mod3 ≡ → ≡ , ( ) 35 20 mod5 ≡ , так как числа 3 и 5 являются делителями числа 15 .