Пункт 21. Порівняння будь-якого степеня за складним модулем.

Теорема 1. Якщо числа m₁, m₂,…m_k попарно взаємно прості, то порівняння f(x)º0(mod m₁m₂ … m_k ) рівносильне системі порівнянь:

При цьому, якщо Т₁, Т₂, ..., Т_к — кількість розв’язків окремих порівнянь цієї системи за відповідними модулями, то кількість розв’язків Т вихідного порівняння дорівнює Т₁Т₂...Т_к.

Доказ. Перше твердження теореми (про рівносильність системи і порівняння) очевидно, тому що якщо aºb(mod m), то aºb(mod d), де d ділить m. Якщо ж aºb(mod m₁) і aºb(mod m₂), то aºb(mod HСK (m₁, m₂)), де НСК (m₁, m₂)– найменше спільне кратне m₁ і m₂. (Згадайте властивості порівнянь з пункту 16).

Перейдемо до другого твердження теореми (про кількість розв’язків порівняння).

Кожне порівняння f(x)º 0(mod m_s) виконується тоді і тільки тоді, коли виконується одне з T_s порівнянь виду x º b_s(mod m_s), де b_s набувають значення лишків розв’язків порівняння f(x)º 0(mod m_s). Усього різних комбінацій таких найпростіших порівнянь

Т₁Т₂...Т_k штук. Усі ці комбінації, за лемою 2 пункту 19, приводять до різних класів лишків за mod(m₁m₂…m_k)...

Отже, розв’язування порівняння зводиться до розв’язування порівнянь виду f(x)º 0(mod p^a). Виявляється, що розв’язування цього останнього порівняння, у свою чергу, зводиться до розв’язування деякого порівняння g(x)º 0(mod p) з іншим многочленом у лівій частині, але вже з простим модулем, що було розглянуто в попередньому пункті. Зведемо розв’язування порівняння f(x)º0(mod p^a) до розв’язування порівняння g(x)º 0(mod p).

Процес зведення.

Очевидно, що з виконання порівняння f(x)º 0(mod p^a) випливає те, що х підходить у порівняння f(x)º0(mod p). Нехай xº x₁(mod p) – який-небудь розв’язок порівняння f(x)º 0(mod p). Це означає, що

x = x₁ + p × t₁, де t₁ Î Z.

Підставимо це х у порівняння f(x)º0(mod p²). Одержимо порівняння

f(x₁+p× t₁)º 0(mod p²),

яке теж, мабуть, виконується.

Розкладемо далі ліву частину отриманого порівняння за формулою Тейлора за степенями (х - х₁):

Оскільки x=x₁+p× t₁, то

.

Зауважимо, що число f^(k)(x₁)/ k! завжди ціле, бо f(x₁+p× t₁) – многочлен з цілими коефіцієнтами. Тепер у порівнянні

f(x₁+p×t₁)º 0(mod p²)

можна зліва відкинути члени, кратні р²:

.

Розділимо останнє порівняння і його модуль на р:

.

Зауважимо знову, що f(x₁)/ p – ціле число, тому що f(x₁)º0(mod p). Далі обмежимося випадком, коли значення похідної f¢ (x₁) не ділиться на р. У цьому випадку існує єдиний розв’язок порівняння першого степеня

 відносно t₁:                                           t₁ºt₁^Ñ (mod p).

Це означає, що t₁=t₁^Ñ +p×t₂, де t₂ Î Z, і

.

Підставимо це x=x₂ +p²t₂ у порівняння f(x)º 0(mod p³) (але тепер це порівняння за mod p³), розкладемо його ліву частину за формулою Тейлора за степенями (х-х₂) і відкинемо члени, кратні p³:

f(x₂)+(f¢ (x₂)/1!)× p²t₂ º0(mod p³).

Поділимо це порівняння і його модуль на р²:

f(x₂)/p²+f¢ (x₂)× t₂º0(mod p).

Знову ж f(x₂)/p² – ціле число, адже число t₁^Ñ таке, що f(x₁+p× t₁^Ñ )º0(mod p²). Крім того, x₂ºx₁(mod p), значить f¢ (x₂)º f¢ (x₁)(mod p), тобто f¢ (x₂), як і f¢(x₁), не ділиться на р. Маємо єдиний розв’язок порівняння першого степеня f(x₂)/p²+f¢ (x₂)× t₂)º0(mod p) відносно t₂:

t₂ºt₂^Ñ (mod p).

Це означає, що t₂= t₂^Ñ +p×t₃, де t₃ÎZ, і

і процес продовжується далі, аналогічно попереднім крокам, до досягнення степеня p^a, у якому стоїть просте число р у модулі вихідного порівняння f(x)º0(mod p^a).

Отже:

Всякий розв’язок xºx₁(mod p) порівняння f(x)º0(mod p), за умови p/f¢¢ (x₁), дає один розв’язок порівняння f(x)º0(mod p^a) виду xºx_a+p^at_a, тобто xºx_a(mod p^a).

Приклад. Розв’язати порівняння x⁴+7 x+4º 0(mod27).

Розв’язування. 27=3³. Можна перевірити перебором повної системи лишків за mod3, що порівняння x⁴+7 x+4º0(mod3) має єдиний розв’язок xº1(mod3).

f¢ (x)=(4 x³+7)½ _xº1º2(mod3),

тобто не ділиться на р=3. Далі:

x₁=1+3× t₁

f(1)+ f¢ (1) 3 × t₁º0(mod3²)

Шукаємо t₁:

3+3 t₁×2º0(mod9),

після ділення на р=3:

1+2 t₁º0(mod3),

t₁º1(mod3) - єдиний розв’язок. Далі:

t₁=1+3 t₂,    x=1+3 t₁=4+9 t₂,

f (4)+9× t₂× f¢ (4)º 0(mod p³=27),    18+9× 20× t₂º0(mod27),

і, після ділення на p²=9, шукаємо t₂:

2+20 t₂º0(mod3),

t₂º2(mod3),     t₂=2+3 t₃,

звідки

x=4+9×(2+3 t₃)=22+27 t₃.

Отже, єдиним розв’язком вихідного порівняння є xº22(mod27).

Наступна теорема відноситься до специфічного виду порівнянь.