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

Пусть р – простое число, и пусть задано сравнение вида f(x)≡0(mod p), где f(x)=axⁿ+a₁x^n—1+…+a_n *. Тогда справедлива

Теорема 1:

Сравнение вида * равносильно сравнению степени, не выше р—1.

Доказательство:

Деля f(x) на (x^p—x) с остатком, имеем f(x) =(x^p—x)Q(x)+R(x).

Так как x^p—x≡0(mod p), то f(x)≡R(x)(mod p), а степень многочлена R(x) не выше, чем р–1. Что и требовалось доказать.

□

Теорема 2

Если сравнение * имеет более n решений, то все коэффициенты многочлена f(x) кратны р.

Доказательство:

Пусть * имеет хотя бы n+1 решение, и вычеты этих решений суть x₁, x₂, … , x_n, x_n+1.

Тогда многочлен f(x) можно представить в виде

f(x)=a(x—x₁)(x—x₂)(x—x₃)…(x—x_n)+ **

+b(x—x₁)(x—x₂)…(x—x_n—1)+

+c(x—x₁)(x—x₂)…(x—x_n—2)+

……...

+l(x—x₁)+m.

Справедливость этого равенства проверяется раскрытием скобок в правой части.

Полагая в этом равенстве x=x₁, убеждаемся, что p\m, полагая x=x₂ и учитывая, что p\m, убеждаемся, что р\l. Полагаем, что x=x₃, x=x₄, …, x=x_n+1 и последовательно убеждаемся, что p\c, p\b, p\a, то есть все коэффициенты из ** делятся на p.

Учтем, что a=a, , , … , , то есть коэффициенты из * являются линейными комбинациями коэффициентов из **, а значит a, a₁, a₂, …, a_n кратны р как линейные комбинации чисел, кратных р.

□