Сравнения высших степеней по простому модулю
Пусть р — простое, f(x) — многочлен степени п с целыми коэффициентами.
/(%) = ахп + арсп~г 4-----1- ап_г 4- ап (2.252)
Рассмотрим сравнения вида /(%) = 0(modp) (2.253)
Теорема 2.61
Любое сравнение вида /(х) = 0(то dp), где р - простое, a f(x) -множество с целыми коэффициентами, равносильно некоторому сравнения, степени не выше р-1.
Доказательство. Запишем деление многочлена f(x) на многочлен хр — х:
f(x) = (хр - х) ? q(x) + т(х) (2.254)
(степень остатка т(х) не выше р-1)
Тогда имеем:
/(х) = 0(mod р) (2.255)
(хр — х) • q(x) + т(х) = 0(mod р) (2.256)
Так как
хр — х = 0(modp) (Теорема Ферма), (2.257)
то
/(х) = T(x)(mod р) (2.258)
Следовательно, исходное сравнение равносильно сравнению
т(х) = 0 (mod р). (2.259)
То есть получили, что произвольное сравнение
/(х) = O(modp), (2.260)
где р - простое число действительно равносильно некоторому сравнению, степени не выше р-1).
Ч.т.д.
Доказанное теорема позволяет на практике свести решение сравнения высокой степени к решению сравнения более низкой степени.
Теорема 2.62
Если сравнение ахп + сцх”-1 + ••• + ап_г + ап = 0 (modp). Степени п по простому модулю р имеет более п различных решений, то все коэффициенты множества f(x) кратны р.
Доказательство. Предположим, что сравнение
ахп + бцх”-1 + —I- ап_г + ап = 0 (mod р) имеет п+1 решений.
Запишем наименьшее неотрицательные вычеты этих решений:
х1,х2,...,хп+1
Тогда множества f(x) можно представить в виде:
/(х) = а(х - xt)(x - х2) ... (х - xn_t)(x - хп)
+ b(x- xj(x - х2) ... (х - хп_2)(х - xn_t)
+ с(х — хД(х — х2) ... (х — хп_2) + к(х — Хі)(х — х2) + 1(х — хг)
+ т (2.288)
Причем, коэффициенту Ьнужно взять равным коэффициенту при хл-1 в разности
/(х) - а(х - хД(х - х2) ... (х - хп), (2.289) коэффициент с нужно взять равным коэффициенту при хп~2 в разности
/(%) — а(х — хД ... (х — xn_t) (2.290)
и так далее.
Теперь пологая последовательно
х = х15х = х2,х = хп+1 (2.291)
получим:
- 1) /(хі) = m = 0(modp), что означает, что т кратно р;
- 2) f (х2) = иг + Z(x2 — Xi) = Z(x2 — хД = (mod р) (2.292)
то есть /кратно р, так как х2 — хг не кратно рпоскольку х2<ри хг<р.
3) f(x3)=k(x3 — хД(х3 ~ х2)= 0(modp), что означает к:р и так далее.
Таким образом, получилось, что все коэффициенты a, b, с,..., I, к, кратны р, но поскольку коэффициенты a, alf..., ап являются суммами чисел кратных р, то и они сами кратны р.
Ч.т.д.
Замечание. Если модуль р - число составное то сравнение
ахп 4- «іХ”-1 4-----1- an_j 4- ап = 0 (mod р) (2.293 )
может иметь и более «решений, при этом коэффициенты a, alf..., ап могут быть не обязательно кратными модулю р.
Например:
х = l(mod 16)
х = 7 (mod 16)
х = 9 (mod 16)
х = 15 (mod 16)
Сравнение любой степени по составному модулю
Теорема 2.63
Если m15 т2,.. .тк - попарно простые, то сравнение
f(x) = 0 (modm1, т2,...тк (2.294)
|
равносильно системе |
г/(х) = 0 (mod тД /(х) = 0 (mod т2) (2.295) |
./(х) = 0 (mod тк>>
При этом число Т - решений сравнения (2.294)равно произведению числа решений Тг, Т2,...Тк сравнений системы (2.295):
т= Тг -Т2 -... -Тк (2.296)
Доказательство. Первая часть теоремы следует из свойств сравнений:
- если сравнение а = b имеет место по нескольким модулям, то оно имеет место и по модулю, равному наименьшему общему кратному этих модулей.
- если сравнение имеет место по модулю т, то оно имеет место и по модулю d, равному делителю числа т.
Вторая часть теоремы следует из того, что каждое сравнение
f(x) = 0 (modms) (2.297)
выполняется тогда и только тогда, когда выполняется одно из Ts сравнений вида
х = bs(modms), (2.298)
где bs пробегает все вычеты решений сравнения
f(x) = 0 (modms). (2.299)
При этом возможно всего Т = Т^-Т^-... ? ^различных комбинаций вида
х= bdmodmi),х= b2(modm2), ... ,х= bk(modmk). (2.300) Все эти сравнения приводят к различным классам по модулю
m-t, т2,...тк.
Например, решим сравнение х4 + 2х3 + 8х + 9 = 0 (mod 35).
Решение. Так как 35 = 5 ? 7, то заданное сравнение равносильно системе Гх4 4- 2х3 + 8х + 9 = 0 (mod 35) (х4 + 2х3 + 8х + 9 = 0 (mod 7)
Первое сравнение системы имеет решения
х = 1 (mod5),x = 4 (mod 5).
Решение второго сравнения системы:
х = 3 (mod 7)
х = 5 (mod 7)
х = 6 (mod 7)
Таким образом, исходное сравнение имеет 2-3 = 6 решений.
Для того, чтобы найти эти решения необходимо решить шесть систем вида
х = b1(mod тг)
х = b2(modm2) (2.301)
при b± = 1; 4, а Ь2 = 3; 5; 6.
Так как
- 35 = 7 • 5 = 5 ? 7
- 7-3 = 7 (mod 5),
- 5-3 = 7 (mod 7),
то совокупность значений х, удовлетворяющей системе (2.301) запишем в виде х = 21b± + 15b2(mod 35).
Таким образом, решением заданного в задаче сравнения будут х = 6; 19; 24; 26; 31; 34(mod 35).
