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

Сначала рассмотрим случай, когда модуль сравнения есть степень простого числа, то есть m=pk, k≥2. Если fx – многочлен с целыми коэффициентами и целое число a удовлетворяет сравнению fx≡0 mod pk, то pk нацело делит fa. Но в этом случае и p нацело делит fa, то есть a удовлетворяет сравнению fx≡0 mod p. Тогда можно сделать два вывода.
1. Если сравнение fx≡0 mod p не имеет решений, то ни при каком k≥2 сравнение fx≡0 mod pk также не имеет решений.
2. Для каждого числа a, удовлетворяющего сравнению fx≡0 mod pk, найдется решение сравнения fx≡0mod p, которому принадлежит a.
Таким образом, решение сравнений по модулю равному степени простого числа p сводится:
к выявлению разрешимости сравнения по простому модулю p,
к поиску решений сравнения по модулю pk, принадлежащих фиксированному решению по простому модулю.
Второй шаг основан на теореме 7.
Теорема 9. Пусть fx – многочлен с целыми коэффициентами и x1 – целое число, удовлетворяющее условиям
fx1≡0 mod p, f'x1≢0 mod p.
Тогда при любом k≥1 существует единственное решение сравнения fx≡0 mod pk, принадлежащее классу вычетов x≡x1 mod p.
Доказательство

. Докажем теорему с помощью индукции по степени модуля k. При k=1 очевидно, что теорема выполняется.
Предположим, что утверждение теоремы справедливо для некоторого k≥1. Тогда существует единственное целое число a, удовлетворяющее условиям
fa≡0 mod pk, 0≤apk, a≡x1 mod p.
Найдем все такие целые числа b, что
fb≡0 mod pk+1, 0≤bpk+1, b≡x1 mod p. (12)
Первое из данных условий показывает, что fb нацело делится на pk,а, значит, наименьший неотрицательны вычет класс b по модулю pk равен a. Тогда b=a+pkt, где t∈Z, 0≤tp.
Многочлен
fa+x=x0+c1x+c2x2+… 13
имеет целые коэффициенты. Подставляя в это равенство x=0, находим c0=fa. Продифференцировав это равенство и также подставляя x=0, получаем c1=f'a. При x=pkt из (13) следует сравнение
fb≡fa+f'apkt mod pk+1.
Так как fa нацело делится на pk и fb нацело делится на pk+1, то разделив обе части сравнения на pk, получим
0≡fapk+f'at mod p.
Учитывая теперь, что a≡x1 mod p, получаем, что f'a≡f'x1 mod p и
f'x1t+fapk≡0 mod p. (14)
По условию теоремы f'x1 не делится нацело на p. Тогда по теореме 2 сравнение (14) разрешимо относительно t и имеет единственное решение