Сравнения любой степени по простому модулю
Пусть p - простое. Докажем общие теоремы, относящиеся к сравнению вида
f(x) º 0(mod p); f(х) = ахn + a1xn-1 + ... + аn.
(1)Теорема 1: Сравнение вида (1) равносильно сравнению степени не выше p - 1.
Доказательство: Деля f(x) на xp - x, имеем
f(x) = (xp - x)Q(x) + R(x),
где степень R(x) не выше p - 1. А так как хр - x º 0(mod p), то f(x) º R(x)(mod p), откуда и следует указанная теорема.
Теорема 2: Если сравнение (1) имеет более чем n решений, то все коэффициенты f(x) кратны р.
Доказательство: Пусть сравнение (1) имеет, по крайней мере, n + 1 решение. Обозначая буквами xl, х2, ..., хn, хn+1 вычеты этих решений, мы можем f(x) представить в виде
f(x) = a(x – x1)(x – x2) ... (x – xn-2)(x – xn-1)(x – xn) +
+ b(x – x1)(x – x2) ... (x – xn-2)(x – xn-1) +
+ c(x – x1)(x – x2) ... (x – xn-2) +
+…………….............+
+ k(x – x1)(x – x2) +
+ l(x – x1) +
+ m. (2)
Действительно, преобразовав раскрытием скобок произведения правой части в многочлены, мы b возьмем равным коэффициенту при xn-1 разности между f(x) и первым многочленом, затем с возьмем равным коэффициенту при xn-2 разности между f(x) и двумя первыми многочленами и т. д.
Полагая в (2) последовательно x = x1, x2, ..., xn, xn+1, убеждаемся в том, что все m, l, k, ..., с, b, а кратны р. Значит, и все a, al, ..., аn кратны p (как суммы чисел, кратных p).
Теорема 3: При простом p справедливо сравнение (теорема Вильсона)
1?2 ... (p - 1) + 1 º (mod p). (3)
Доказательство: Если p = 2, то теорема очевидна. Если же p > 2, то рассмотрим сравнение
(x - 1)(x - 2) ... (x - (p - 1)) - (xp-1 - 1) º 0(mod p);
оно степени не выше p - 2 и имеет p - 1 решение, именно решения с вычетами 1, 2, ..., р - 1. Следовательно, по теореме с все его коэффициенты кратны p; в частности, на p делится и свободный член, равный как раз левой части сравнения (3).
Пример: Имеем 1?2?3?4?5?6 + 1 = 721 º 0(mod 7). 5