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

52 • Общий делитель одной части сравнения и модуля является делителем другой части сравнения : (mod ) & & m n p m lk p rk n sk ≡ = = → = . (5.22) Здесь , , , , , , , ( , 0) m n p l k r s k r ∈ > Z – некоторые числа . Число 0 k > является делителем чисел m и p , следовательно , является делите - лем числа n . Отсюда следует , что HOD ( наибольшие общие делители ) пар чисел ( ) , m p и ( ) , n p совпадают : ( ) ( ) , , HOD m p HOD n p = . В частности , если ( ) ( ) , 1 , 1 HOD m p HOD n p = → = , т . е . если числа m , p взаимно просты , то и числа n , p взаимно просты . Доказать утверждения (5.9) – (5.22) предлагается самостоя - тельно . Вернемся к общим определениям . Возможно другое , фор - мальное , определение бинарного отношения . Рассмотрим упорядоченные пары элементов , связанных признаком R . Эти пары образуют подмножество декартова квад - рата 2 A множества A , которое также обозначается символом R : ( ) { } 2 , : R a b aRb A = ⊂ . Очевидно , множество 2 R A ⊂ однозначно определяется при - знаком R . Поэтому под бинарным отношением R во ( на ) множе - стве A можно понимать соответствующее данному признаку под - множество 2 R A ⊂ . Запись aRb эквивалентна записи ( , ) a b R ∈ . Таким образом , получаем второе определение бинарного от - ношения . Бинарным отношением на ( или во ) множестве A называется любое подмножество R декартова квадрата 2 А . Данное определение является более строгим , формальным и сводит понятие бинарного отношения к фундаментальному по - нятию множества , что позволяет использовать методы теории мно -