Сравнения любой степени по простому модулю
Пусть р – простое число, и пусть задано сравнение вида f(x)≡0(mod p), где f(x)=axn+a1xn—1+…+an *. Тогда справедлива Теорема 1: Сравнение вида * равносильно сравнению степени, не выше р—1. Доказательство: Деля f(x) на (xp—x) с остатком, имеем f(x) =(xp—x)Q(x)+R(x). Так как xp—x≡0(mod p), то f(x)≡R(x)(mod p), а степень многочлена R(x) не выше, чем р–1. Что и требовалось доказать. □ Теорема 2 Если сравнение * имеет более n решений, то все коэффициенты многочлена f(x) кратны р. Доказательство: Пусть * имеет хотя бы n+1 решение, и вычеты этих решений суть x1, x2, … , xn, xn+1. Тогда многочлен f(x) можно представить в виде f(x)=a(x—x1)(x—x2)(x—x3)…(x—xn)+ ** +b(x—x1)(x—x2)…(x—xn—1)+ +c(x—x1)(x—x2)…(x—xn—2)+ ……... +l(x—x1)+m. Справедливость этого равенства проверяется раскрытием скобок в правой части. Полагая в этом равенстве x=x1, убеждаемся, что p\m, полагая x=x2 и учитывая, что p\m, убеждаемся, что р\l. Полагаем, что x=x3, x=x4, …, x=xn+1 и последовательно убеждаемся, что p\c, p\b, p\a, то есть все коэффициенты из ** делятся на p. Учтем, что a=a, , , … , , то есть коэффициенты из * являются линейными комбинациями коэффициентов из **, а значит a, a1, a2, …, an кратны р как линейные комбинации чисел, кратных р. □ Сравнения любой степени по составному модулю. Теорема Если m1, m2, … , mk – попарно простые числа, то сравнение f(x)≡0(mod m1·m2·…·mk) * равносильно системе ** , причем, если первое сравнение имеет T1 решений по модулю m1, второе – T2 решений модулю m2, …, k-е сравнение имеет Tk решений по модулю mk, то исходное сравнение будет иметь T=T1·T2·…·Tk решений по модулю m1·m2·…·mk. Доказательство: Равносильность сравнения и системы очевидна и следует из свойств 12 и 13 сравнений. Утверждение о количестве решений следует из того, что каждое сравнение f(x)≡0(mod ms) *** выполняется тогда и только тогда, когда выполняется одно из Ts сравнений вида x≡bs(mod ms) (где bs пробегает вычеты решений сравнения ***). Причем возможно всего T=T1·T2·…·Tk различных комбинаций вида x≡b1(mod m1), x≡b2(mod m2),…, x≡bk(mod mk), которые приводят (по китайской теореме об остатках) к различным классам вычетов по модулю m1·m2·…·mk. □ Из доказанной теоремы следует, что решение сравнения вида сводится к решению сравнений вида . А решение сравнение вида f(x)≡0(mod pα) может быть найдено, если известно решение сравнения f(x)≡0(mod p). Покажем это. Пусть x≡x1(mod p) – решение сравнения f(x)≡0(mod p). Тогда x можно представить в виде x=x1+pt1, где . Подставляя такое x в сравнение f(x)≡0(mod p2) и применяя формулу Тейлора (учитывая, что f(x) – многочлен, x1 – целое число, поэтому ), получаем f(x1)+pt1f '(x1)≡0(mod p2). Поскольку f(x1)≡0(mod p), то p\f(x1), а значит можно сократить в получившемся выражении на p правую, левую части и модуль. Получим: Если f '(x1) не делится на р, то данное сравнение имеет одно решение: (т.е. ) Подставляя полученное x в сравнение f(x)≡0(mod p3), имеем f(x2)+p2t2f '(x2)≡0(mod p3), откуда, сократив правую, левую части и модуль на p2 , получим [Здесь f '(x2) не может быть кратно р, если f '(x1) не кратно p, т.к. x2≡x1(mod p), а значит, f '(x2) ≡ f '(x1) (mod p)] Тогда сравнение имеет одно решение , или, что то же самое, , откуда получаем решение по модулю p3 : x=x3+p3t3. Продолжим этот процесс до тех пор, пока не будет решено сравнение по модулю pα. Итак, по данному решению сравнения f(x)≡0(mod p) можно найти решение сравнения f(x)≡0(mod pα). Пример: Требуется решить сравнение x3+9x—1≡0 (mod 125). Известно, что сравнение x3+9x—1≡0 (mod 5) имеет одно решение: x≡2(mod 5), или x=2+5t1. Поскольку модуль «5» небольшой, а общих подходов к сравнениям высоких степеней мы пока не знаем, то этот корень нашли простым перебором, попутно убедившись в его единственности. Подставим получившееся x в сравнение по модулю 25: (2+5t1)3+9(2+5t1)—1≡0 (mod 25).
Решим это сравнение. 8+4·5t1+2·(5t1)2+(5t1)3+18+9·5t1—1≡0 (mod 25) 25+13·5t1+25·(5t13+2 t12) ≡0 (mod 25) 13·5t1≡0 (mod 25) 13t1≡0 (mod 5) t1≡0 (mod 5) Или, что то же самое, t1=0+5t2, откуда решение по модулю 25 есть x=2+25t2. Подставим полученное x в сравнение по модулю 125: (2+25t2)3+9(2+25t2)—1≡0 (mod 125) Решим это сравнение. 8+4·25t2+2·(25t2)2+(25t1)3+18+9·25t1—1≡0 (mod 125) 25+13·25t2+625·(25t23+2t22) ≡0 (mod 125) 25+13·25t2≡0 (mod 125) 1+13t2≡0 (mod 5) 13t2≡—1 (mod 5) 3t2≡4 (mod 5) Получили сравнение первой степени. Решим его. Отыщем 3-1(mod 5), для чего, как всегда, воспользуемся расширенным алгоритмом Евклида: 5=3+2 3=2+1 2=1+0 1=3—2=3—(5—3)=2·3—1·5. 2≡3-1(mod 5). Тогда решением сравнения относительно t2 будет t2≡2·4 (mod 5) t2≡3 (mod 5) Или, что то же самое, t2=3+5t3, откуда решение по модулю 125 есть x=2+25(3+5t3)=2+75+125t3=77+125t3, или, что то же самое, x≡77 (mod 125).
Популярное: Как выбрать специалиста по управлению гостиницей: Понятно, что управление гостиницей невозможно без специальных знаний. Соответственно, важна квалификация... Почему человек чувствует себя несчастным?: Для начала определим, что такое несчастье. Несчастьем мы будем считать психологическое состояние... Генезис конфликтологии как науки в древней Греции: Для уяснения предыстории конфликтологии существенное значение имеет обращение к античной... Личность ребенка как объект и субъект в образовательной технологии: В настоящее время в России идет становление новой системы образования, ориентированного на вхождение... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (2138)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |