Сравнения с одним неизвестным
Будем рассматривать сравнения вида a0xn + a1xn-1 + … + an≡ 0 (mod m) (*). Если a0 не делится на m, то n называется степенью сравнения. Решить сравнение – значит найти все x, ему удовлетворяющие. Два сравнения, которые удовлетворяют одни и те же значения x, называются равносильными. Если сравнению (*) удовлетворяет какое-то x=x1, то ему же будут удовлетворять все числа, сравнимые с x1 по модулю m: x ≡ x1(mod m). Весь класс чисел, сравнимых с x1 по модулю m считается за одно решение. Таким образом, (*) будет иметь столько решений, сколько вычетов из полной системы ему удовлетворяет. Пример: x5+x+1=0 (mod 7) удовлетворяют x ≡ 2 (mod 7) и x ≡ 4 (mod 7) – 2 решения. Сравнения первой степени.
Любое сравнение первой степени можно привести к виду ax ≡ b (mod m). Рассмотрим случай, когда (a, m)=1. Согласно утверждению 2 пункта 3 §3, когда x пробегает полную систему вычетов по модулю m, ax тоже пробегает полную систему вычетов по по модулю m. Следовательно, при одном и только одном значении x из полной системы вычетов, ax будет сравнимо с b, т.е. при (a, m)=1 сравнение имеет ровно 1 решение. Нахождение решения: Так как (a, m) = 1, то по теореме обратимости a-1 , и тогда исходному сравнению равносильно x ≡ a-1∙b (mod m). Пусть теперь (a,m)=d>1. Для того, чтобы сравнение имело решение, необходимо, чтобы d\b, иначе сравнение невозможно (свойство сравнений №14). Если же a=a1d, b=b1d, m=m1d , то исходному сравнению равносильно a1x≡b1(mod m1), причем (a1,m1)=1 сравнение имеет 1 решение по mod m1: x≡x1(mod m1), или d решений по модулю m: x≡ x1 (mod m), x≡ x1+m1(mod m), x≡x1+2m1(mod m), … x≡x1+(d–1)m1(mod m). Пример 1. Решить сравнение 6x = 5 (mod 35). Вычислим НОД(6, 35), пользуясь алгоритмом Евклида: 35 = 6∙5+5, 6 = 1∙5 +1 5 = 5∙1+0 НОД(6, 35)=1. Вычислим обратный элемент к 6 по модулю 35, пользуясь расширенным алгоритмом Евклида: 1 = 6–5=6–(35–6∙5)=6–35+6∙5= 6∙6–35 6-1 = 6 (mod 35). Домножим правую и левую части исходного сравнения на 6: 6-1∙6x≡6-1∙5(mod 35) 1∙x≡6∙5(mod 35) Ответ: x ≡ 30 (mod 35)
Пример 2. Решить сравнение 18x = 6 (mod 24). Вычислим НОД(18, 24), пользуясь алгоритмом Евклида: 24 = 18 + 6; 18 = 2∙6+0 НОД(18, 24)=6. Правая и левая части сравнения, а также модуль, делятся на 6. Разделим исходное сравнение на 6 и получим равносильное сравнение: 3x ≡ 1 (mod 4) *. Вычислим НОД(3, 4), пользуясь алгоритмом Евклида: 4 = 1∙3 + 1; 3 = 3∙1 + 0 НОД(3, 4)=1. Вычислим обратный элемент к 3 по модулю 4, пользуясь расширенным алгоритмом Евклида: 1=4–3 3-1 = –1(mod 4). Домножим правую и левую части сравнения (*) на –1: 3-1∙3x=–1∙1 (mod 4) x≡ –1 (mod 4). Или, переводя решение в систему наименьших неотрицательных вычетов, x≡ 3 (mod 4). Ответ: получили 6 решений по модулю 24: x≡ 3 (mod 24); x≡ 7 (mod 24); x≡ 11 (mod 24); x≡ 15 (mod 24); x≡ 19 (mod 24); x≡ 23 (mod 24). Система сравнений первой степени. Китайская теорема об остатках.
Рассмотрим систему сравнений * От системы сравнений вида aix ≡ bi (mod mi) можно перейти к данной способом, указанным в п.1.
Популярное: Почему человек чувствует себя несчастным?: Для начала определим, что такое несчастье. Несчастьем мы будем считать психологическое состояние... Как выбрать специалиста по управлению гостиницей: Понятно, что управление гостиницей невозможно без специальных знаний. Соответственно, важна квалификация... Почему двоичная система счисления так распространена?: Каждая цифра должна быть как-то представлена на физическом носителе... Почему люди поддаются рекламе?: Только не надо искать ответы в качестве или количестве рекламы... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (2353)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |