Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
|
Отношение сравнения, свойства сравненийПусть m – фиксированное натуральное число. Все целые числа по отношению к числу m разбиваются на m классов, если отнести к одному классу числа, дающие один и тот же остаток при делении на m. Числа, относящиеся к одному классу, называется сравнимыми, а теория, изучающая свойства классов, теорией сравнений. Определение 1. Пусть m – натуральное число. Целые числа a и b называется сравнимыми по mod m, если их разность a – b m. Запись a ≡ b (mod m). Читается «а сравнимо с b по mod m». Сравнение представляет собой соотношение между 3 числами: a, b и m, причем m играет своего рода эталона сравнения – называется модулем. Определение 2. Целые числа a и b называется сравнимыми по mod m, если остаток от деления этих чисел на m равны. Предложение. Определения 1 – 2 равносильны. Следствия. 1. a m ó a ≡ 0 (mod m) Всякое число, кратное m, сравнимо с нулем по mod m. 2. a =mg + r ó a ≡ r (mod) 0 ≤ r < m Всякое целое всегда сравнимо с остатком k, получающимся при делении его на m. Свойства сравнений. 10. рефлексивность: а ≡ а (mod m) а Є Z a – a = 0 m 20. симметричность: а ≡ b (mod m) => b ≡ а (mod m) a – b m => b – a m 30. транзитивность: а ≡ b (mod m) Λ b ≡ c (mod m) => a ≡ c (mod m) a – b m Λ b – c m => (a – c) + (b – c) =a – c m Вывод. Отношение сравнения на множестве Z по mod m является отношением эквивалентности => Z разбивается на непересекающийся между собой классы эквивалентности. Эти классы – называются классами вычетов по модулю m или просто классами по mod m. При этом числа из одного класса попарно сравнимы между собой, а числа из различных классов не сравнимы между собой => класс по mod m состоит из чисел, дающих один и тот же остаток при делении на m. 40.Сравнения по одному и тому же модулю можно почленно складывать (вычитать) а1 ≡ b1 (mod m) а2 ≡ b2 (mod m) ______________ a1 ± a2 ≡ b1 ± b2 (mod m) a1 – b1 m => (a1 ± a2) - (b1 ± b2) =(a1 – b1) ± (a2 – b2) m a1 ± a2 ≡ b1 ± b2(mod m) a2 – b2 m Следствия. 1.Любое слагаемое из одной части сравнения можно перенести в другую с противоположным знаком. а + b ≡ с (mod m) => а ≡ с – b (mod m) - b ≡ - b (mod m) _______________ а ≡ с – b (mod m) 2. К любой части сравнения можно прибавить (отнять) число, кратное модулю. а ≡ b (mod m) => а ≡ b – mk (… m) 0 ≡ mk (… m) 50 Сравнения по одному и тому же mod можно почленно перемножить. а1 ≡ b1 (mod m) а2 ≡ b2 (… m) _________________ a1a2 ≡ b1b2 (… m) a1a2 – b1b2 = a1a2 – b1b2 + a1b2 – b1b2 = a1 (a2 – b2) + b2 (a1 – b1) m Следствия. 1)Обе части сравнения можно умножить на одно и то же число a ≡ b (… m) => ac ≡ bc (mod m) => a – b =mg => ac – bc ≡ m (gc) 2) Обе части сравнения можно вознести в одну и ту же натуральную степень. a ≡ b (mod m) => an ≡ bn (mod m) 60 Обе части сравнения можно сократить на множитель, взаимно простой с модулем. aс ≡ bс (mod m) Λ (c, m) = 1 => a ≡ b (mod m) => ac – bc m => c (a – b) m Λ (c, m) = 1 =>a – b m 70 Обе части сравнения и модуль можно умножить на одно и то же число. a ≡ b (mod m), r (mod m) Є Z => ak ≡ bk (mod mr) a – b = mg => ak – bk = (mr)g k Є Z 80 Если ak ≡ bk (mod mk) => a ≡ b (mod m) где r, m – произв. нат. ч. Доказательство- самостоятельно. 90 a ≡ b (mod m) Λ m d => a ≡ b (mod m) => a – b m и m d => a – b d 100 a ≡ b (mod m) => множество общих делителей a и m совпадает с множеством общих делителей b и m. В частности, (a, m) = (b, m) a – b m => a – b = mg и b = a – mg, т.е. общий делитель чисел а и m является общим делителем чисел b и m и наоборот. Поскольку пара a и m и пара b и m имеют одни и те же общие делители, то и (a, m) = (b, m). Другими словами: если одна часть сравнения и модуль делятся на какое – либо число, то и другая часть сравнения должна на то же число a ≡ b (mod m) 110 a ≡ b (mod m1) a ≡ b (mod m2) ------------------- a ≡ b (mod mk) где m ≡ [m1, …, mk] 120 Пусть f(x) – многочлен с целыми коэффициентами, a ≡ b (mod m) => f(a) ≡ f(b) (mod m) Доказательство: Пусть f(x) = c0 xn + c1 x n-1 + … + cn a ≡ b (mod m) => ak ≡ bk (mod m) k = 0, …, n Умножая обе части на c n-k C n-k ak ≡ C n-k bk (mod m) k = 0, n Складывая полученные сравнения, получим f(a) ≡ f(b) (mod m)
|