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

50 В частности , справедливы утверждения : (mod ) (mod ); m k n p m n k p + ≡ → ≡ − (5.13) (mod ) (mod ); m n p km kn p ≡ → ≡ (5.14) (mod ) (mod ) k k m n p m n p ≡ → ≡ ; (5.15) ( ) ( ) (mod ) (mod ) x y p f x f y p ≡ → ≡ , (5.16) где ( ) f x – целый многочлен с целыми коэффициентами : ( ) 1 0 1 0 n n n n i n i i f x a x a x a a x − − = = + + + = ∑ L . Кроме того , , 0, i i a b i n ≡ = ↔ 0 n n i i i a x − = ≡ ∑ 0 n n i i i b x − = ∑ . (5.17) Это значит , что в многочлене ( ) f x коэффициенты , 0, i a i n = можно заменять числами , 0, i b i n = , равными им по модулю . Таким образом , в равенстве по некоторому модулю можно слагаемые и множители заменять сравнимыми по тому же модулю числами . Например : ( & ) m k n k r m r n + ≡ ≡ → + ≡ , ( mk n ≡ & ) k r ≡ → mr n → ≡ . Показатели степени таким образом заменять нельзя : ( ) 4 2 1 mod5 ≡ , ( ) 4 9 mod5 ≡ , но ( ) 4 9 2 2 mod5 ≡/ . • Обе части сравнения можно делить ( сократить ) на их об - щий делитель , взаимно простой с модулем : ( ) ( ) mod mod m n p m k n k p ≡ → ≡ , (5.18)