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

Перейдем к рассмотрению вопроса о числе решений сравнения n-й степени по простому модулю.
Теорема 3. Сравнение
anxn+…+a1x+a0≡0 mod p (3)
степени n по простому модулю p имеет не более n решений.
Доказательство. Доказательство проведем методом математической индукцией. Если n=0, то сравнение (3) имеет вид a0≡0 mod p, где a0 не делится нацело на p. Тогда сравнение не имеет решений.
Предположим, что сравнение (3) имеет степень n0. Если сравнение имеет решения, то для некоторого целого числа x1 имеем
anx1n+…+a1x1+a0≡0 mod p. (4)
Вычтем сравнение (4) из сравнения (3). Тогда разность членов степени k, k=1, n, имеет вид
akxk-x1k=akx-x1xk-1+xk-2x1+…xx1k-2+x1k-1,
при этом каждая разность содержит линейный множитель x-x1. Поэтому результат вычитания можно записать так:
x-x1bn-1xn-1+…+b1x+b0≡0 mod p, (5)
где bi, i=0, n-1, – некоторые целые числа, при этом bn-1=an.
Рассмотрим другое решение сравнения (4), например, x2. Так как x2≢x1 mod p и модуль p – простой, то из сравнения
x2-x1bn-1x2n-1+…+b1x2+b0≡0 mod p
следует, что
bn-1x2n-1+…+b1x2+b0≡0 mod p,
то есть x2 будет решением сравнения
bn-1xn-1+…+b1x+b0≡0 mod p. (6)
Так как степень сравнения (6) равна n-1, то, по индуктивному предположению, сравнение (6) имеет не более n-1 решений

. Следовательно, исходное сравнение (4) имеет не более n решений. Теорема доказана.
Следствие. Для каждого простого числа p справедливо сравнение
xp-x≡xx-1x-2…x-p+1 mod p,
то есть коэффициенты при одинаковых степенях переменной x в правой и левой частях сравнимы между собой и делятся на p.
Доказательство. Рассмотрим многочлен
fx=xp-x-xx-1x-2…x-p+1∈Zx.
Его степень не превосходит p-1. Если n – наибольшее целое число, такое, что коэффициент при xn в многочлене fx не делится на p, то степень сравнения fx≡0 mod p равна n. Для каждого целого числа a, 0≤a≤p-1, по теореме Ферма имеем
fa=ap-a≡0 mod p.
Значит, число решений сравнения fx≡0 mod p равно p. По теореме 3 выполняется неравенство p≤n. Так как n≤p-1, то получаем противоречие, которое и доказывает, что все коэффициенты многочлена fx делятся на p. Теорема доказана.
Теорема 4. Пусть
fx=xp-xgx+rx, rx∈Zx, degrxp.
Тогда множества целых чисел, удовлетворяющие сравнениям
fx≡0 mod p и rx≡0 mod p,
совпадают.
Доказательство. Для каждого целого числа a по теореме Ферма имеем
fx≡ap-aga+ra≡0⋅ga+ra≡ra mod p,
что и доказывает теорему.
Теорема 5. Если p – простое число, то сравнение
xp-1-1≡0 mod p (7)
имеет точно p-1 решений