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

Теорема 1: Если m₁, m₂, …, m_k попарно простые, то сравнение

f(x) º 0(mod m₁m₂…m_k) (1)

равносильно системе

f(x) º 0(mod m₁), f(x) º 0(mod m₂), ..., f(x) º 0(mod m_k).

При этом, обозначая через T₁, Т₂, ..., T_k числа решений отдельных сравнений этой системы по соответственным модулям и через Т - число решений сравнения (1), будем иметь

T = T₁T₂…T_k.

Доказательство: Первая часть теоремы следует из (глава 3, п. 3, Свойство 3 и Свойство 4). Вторая часть следует из того, что каждое сравнение

f(x) º 0(mod m_s) (2)

выполняется тогда и только тогда, когда выполняется одно из T_s сравнений вида

x º b_s(mod m_s),

где b_s пробегает вычеты решений сравнения (2), причем возможно всего T₁T₂ ... T_k различных комбинации вида

x º b₁(mod m₁), x º b₂(mod m₂), ..., x º b_k(mod m_k),

приводящих (п. 3, теорема 2) к различным классам по модулю

m₁m₂ ... m_k.

Пример: Сравнение

f(x) º 0(mod 35), f(x)=х⁴ + 2х³ + 8x + 9 (3)

равносильно системе

f(x) º 0(mod 5), f(x) º 0(mod 7).

Легко убедимся, что первое сравнение этой системы имеет 2 решения: x º 1; 4(mod 5), второе же сравнение имеет 3 решения: x º 3; 5; 6(mod 7). Поэтому сравнение (3) имеет 2?3 = 6 решений. Чтобы найти эти 6 решений, надо решить 6 систем вида

x º b₁(mod 5), x º b₂(mod 7), (4)

которые получим, заставляя b₁ пробегать значения b₁ = 1; 4, а b₂ пробегать значения b₂ = 3; 5; 6.

35 = 7?5 = 5?7, 7?3 º 1(mod 5), 5?3 º 1(mod 7),

совокупность значений x, удовлетворяющих системе (4), представится в виде (п. 3, Теорема 1)

x º 21b₁ + 15b₂(mod 35).

Поэтому решения сравнения (3) будут

x º 31; 26; 6; 24; 19; 34 (mod 35).

Ввиду (теоремы 1) исследование и решение сравнения

сводятся к исследованию и решению сравнений вида

f(x) º 0(mod p^a); (5)

это же последнее сравнение сводится вообще, как мы сейчас выясним, к сравнению

f(x) º 0(mod p). (6)

Доказательство: Всякое x, удовлетворяющее сравнению (5), необходимо должно удовлетворять и сравнению (6). Пусть

x º x₁(mod p)

- какое-либо решение сравнения (6). Тогда x = x₁ + pt₁, где t₁ - целое. Вставляя это значение х в сравнение

f(x) º 0(mod p²)

и разлагая левую часть по формуле Тейлора, найдем (принимая во внимание, что - целое, и отбрасывая члены, кратные р²)

, .

Ограничиваясь здесь случаем, когда f'(x₁) не делится на p, имеем одно решение:

t₁ º t₁'(mod p); t₁ = t₁' + pt₂.

Выражение для х принимает вид

x = x_l + pt₁' + p²t₂ = x₂ + p²t₂;

вставляя его в сравнение

f(x) º 0(mod p³),

получим

, .

Здесь f'(x₂) не делится на p, так как

x₂ º x₁(mod p), f'(x₂) º f'(x₁)(mod p),

и потому последнее сравнение имеет одно решение:

t₂ º t'₂(mod p), t₂ º t'₂ + pt₃.

Выражение для x принимает вид

x = x₂ + p²t'₂ + р³t₃ = x₃ + р³t₃;

и т. д. Таким путем по данному решению сравнения (6) постепенно найдем сравнимое с ним решение сравнения (5). Итак, всякое решение x º х₁(mod p) сравнения (6) при условии, что f'(х₁) не делится на p, даст одно решение сравнения (5):

x º x_a + p^at_a; x º x_a (mod p^a).

Пример: Решим сравнение

f(x) º 0(mod 27); f(x) = x⁴ + 7х + 4. (7)

Сравнение f(x) º 0(mod 3) имеет одно решение x º 1(mod 3); при этом f'(1) º 2(mod 3) и, следовательно, не делится на 3.

Находим:

x = 1 + 3t₁,

f(1) + 3t₁f'(1) º 0(mod 9); 3 + 3t₁?2 º 0(mod 9),

2t₁ + 1 º 0(mod 3), t₁ º 1(mod 3), t₁ = 1 + 3t₂,

x = 4 + 9t₂,

f(4) + 9t₂f'(4) º 0(mod 27); 18 + 9t₂?2 º 0(mod 27),

2t₂ + 2 º 0(mod 3), t₂ º 2(mod 3), t₂ = 2 + 3t₃,

x = 22 + 27t₃,

Таким образом сравнение (7) имеет одно решение

x º 22(mod 27).

Глава 5