Сравнения по простому модулю. Сравнения по степени простого числа. Сравнения по составному модулю

§4 Сравнении с неизвестной величиной по простому модулю

Теорема 1. Сравнение по простому модулю р, степень которого n≥ р, может быть заменено равносильным ему сравнением степени, меньшей р.

Доказательство. Сначала покажем, что сравнение f(x)≡0(mod р) равносильно сравнению f(x)-(х^p -x)q(х)≡0(mod р), где р - простое, f(x), q(x) € Z[x]. Действительно, если x0 удовлетворяет первому сравнению, то оно удовлетворяет и второму сравнению, так как x0^p -х0 ≡ 0(mod р) (теорема Ферма). Обратно, если х0 удовлетворяет второму сравнению, то есть f(х0) ≡(x0^p-x0)q(x0)(mod p), то х0 удовлетворяет первому сравнению. f(x0)≡0(mod p), так как x0^p-x0≡0(mod p) (теорема Ферма). Равносильность доказана.

Пусть f(х)≡ 0(mod р) - сравнение степени n≥ р. Разделим f(x) с остатком на х^p -x: f(x)= (х^p - x)q(x)+г(х), где степень г(х) меньше p

или г(х) = 0. Легко видно, что q(x) и г(х) с целыми коэффициентами (делим столбиком на многочлен со старшим коэффициентом, равным 1). По Доказанному выше сравнение f(x) ≡ 0(mod р) равносильно сравнению f(x)-(х^p -x)q(x)≡0(mod p), то есть сравнению r(x) ≡ 0(mod p).

Замечание. На практике часто удобнее понижать степень каждого слагаемого многочлена, если его степень не меньше р. Пусть, например многочлен имеет слагаемое степени k и k≥ р. Разделим k с остатком на р-1: k = (p-1)q + r, 0≤r <(p-l). Если х0 не делится на р,

То x0^k=(x0^(p-1))^q*x0^r≡1^q*x0^r≡x0^r (mod p); если же x0:p, то x0^k≡x0^r≡0(mod p). Поэтому для любого целого х0, если r≠ 0, то

х0^k≡ x0^r (mod р). Если же r= 0, то случаи х0:р и х0 не делится на р существенно отличаются. В первом случае x0^k≡ 0(mod р), а во втором

x0^k≡ l(mod р). Однако в любом случае x0^k≡x0^p-1(mod p). Поэтому слагаемое a_k x^k, где k≥р, k=(p-1)q + r, можно заменить а_k x^r, если

r≠0 и а_k x^p-1, если r= 0. При этом получим сравнение, равносильное исходному.

Пример:

Х¹⁶ + 6x¹² + Зх⁸ - 5х⁷ + 2х⁶ – х⁴ - 2 ≡ 0(mod 7)

р-1 = 6; 16 = 6*2 + 4; 12= 6*2; 8 = 6 + 2; 7 = 6 + 1. Сравнение равносильно следующему:

х⁴ + 6х⁶ + Зх² -5х + 2х⁶ — х⁴ — 2 ≡ 0(mod 7)

Или х⁶ +3х² + 2x-2 ≡ 0(mod7). Так как х = 0 не удовлетворяет этому сравнению, то есть х не делится на 7, то х⁶ заменим 1 (х⁶≡ l(mod 7)).

Зх² +2х-1 ≡ 0(mod7). Взяв полную систему вычетов по модулю 7: 0,1, 2,3, - 3, -2, - 1, находим, что х ≡ -2(mod 7) и х ≡ -l(mod 7).

Теорема 2. Сравнение степени n по простому модулю имеет не более n решений.

Доказательство (индукцией по n). Сравнение 1-ой степени по простому модулю р ах≡b(mod р) Имеет 1 решение, так как (а,р) =1.

Пусть сравнение степени n-1 имеет не более чем n-1 решение. Рассмотрим сравнение степени n: f(х) ≡ 0(mod р), (l)

где f(x)€Z, f(x)=a0xⁿ+alx^n-1 +... + аn и (а0,р)=1. Если сравнение (l) не имеет решений, то утверждение верно. Пусть х0 удовлетворяет сравнению (l), то есть f(х0)≡ 0(mod р). Разделим f(х) с остатком на x-x0. По теореме Безу f(x) = (x-x0)g(x)+ f(х0). Так как f(х0) ≡ 0(mod р), то сравнение (l) примет вид (х - х0)g(x) ≡ 0(mod р). Причём g(x) имеет степень n-1, его коэффициенты - целые числа (g(x) вычисляется по схеме Горнера) и его старший коэффициент равен а0. Если класс х1 - другое решение сравнения (l), то (x1-x0)g(x1)≡0(mod p), то если (х1- x0)g(x1): р. Но х1 - х0 не делится на р, так как х0 и х1 не сравнимы по модулю р. Следовательно, g(xl): р, g(x1) ≡0(mod р) и класс х1 - решение сравнения g(x)≡0(mod з). Итак, любое решение сравнения (l), отличное от класса x0, является решением сравнения g(x) ≡ 0(mod р), которое по индуктивному предположению имеет не более чем n — 1 решений. А значит, сравнение (l) имеет не более чем n решений. Теорема доказана.

Пример.

Известно, ЧТО 31 удовлетворяет сравнению 11х² ≡ 65(mod 103). Найти все решения этого сравнения. Так как это сравнение по простому модулю имеет не более двух решений и число - 31 тоже удовлетворяет ему, то имеем: х ≡ ±3l(modl03).

Следствие. Если сравнение а0хⁿ + а1х^n-1 +... + an≡ 0(mod р), где р - простое, имеет более чем n решении, то все коэффициенты а_i (i = 0,1,...,n) делятся на р.

Теорема Вильсона. Если р - простое, то (р - l)!+l ≡ 0(mod р).

Доказательство. Сравнение, очевидно, верно при р = 2. Пусть р > 2. Рассмотрим сравнение (х - 1)(x - 2)...(х - (р - l))-(x^p-1 - l)≡ 0(mod р). Степень сравнения не может быть большей или равной р-1. Однако сравнение имеет р-1 решение: классы 1,2,..., р-1. По следствию из теоремы все коэффициенты сравнения делятся на р. В частности, свободный член (-1)(- 2)...(- (р -1))+1 делится на р. Так как р -1 для р> 2 число чётное, то ((р - l)!+l):р или (р - l)!+l ≡ 0(mod р).