то ab (mod d), де d ділить m. Якщо ж ab (mod m?) І ab (mod m?), То ab (mod HOK (m?, M?)), Де НОК (m?, M?) - Найменше спільне кратне m? і m?.
Звернімося до другого твердженням теореми (про число рішень порівняння). p> Кожне порівняння f (x) 0 (mod m) виконується тоді і тільки тоді, коли виконується одна з T s штук порівнянь виду xbs (mod ms), де b пробігає відрахування рішень порівняння f (x) 0 (mod m) . Всього різних комбінацій таких найпростіших порівнянь
В
Т? Т? ... штук. Всі ці комбінації призводять до різних класів лишків за mod (m? M? ...). p> Лемма 1. Довільний порівняння f (x) 0 (mod p), де р - просте число, рівносильне деякому порівнянні ступеня не вище p-1. p> Доказ. Розділимо f (x) на многочлен - х (В«многочлен розподілу колаВ») із залишком:
(x) = (- х) Q (x) + R (x),
де ступінь залишку R (x) не перевищує р-1. Але ж, по теоремі Ферма, - х 0 (mod p). Це означає, що f (x) R (x) (mod p), а вихідне порівняння рівносильно порівнянні R (x) 0 (mod p). p> За допомогою доведеною леми можна звести рішення високого ступеня до вирішення порівняння меншому ступені.
Лемма 2. . Якщо порівняння а + + ... + 0 (mod p)
ступеня n по простому модулю р має більш n різних рішень, то всі коефіцієнти а,, ..., кратні р.
Доказ. Нехай порівняння а + + ... + 0 (mod p)
має n +1 рішення і,, ...,, - найменші невід'ємні відрахування цих рішень. Тоді, очевидно, многочлен f (x) представимо у вигляді:
(x) = a (() ... () () () + b (() ... () () + c (() ... () + ... + k (() + l (+ m.
Дійсно, коефіцієнт b потрібно взяти рівним коефіцієнту при в різниці f (x) - a (() ... () () (); коефіцієнт с - це коефіцієнт перед в різниці
(x) - a (() ... () () () - b (() ... () (), і т.д. Тепер покладемо послідовно =,, ...,,. Маємо:
) f () = m 0 (mod p), отже р ділить m;
) f () = m + l () l (0 (mod p), отже p ділить l, бо p не може ділити, так як;
) f () k (0 (mod p), отже, р ділить k.
І так далі.
Виходить, що всі коефіцієнти a, b, c, ..., k, l кратні р. Це означає, що всі коефіцієнти ..., теж кратні р, адже вони є сумами чисел, кратних р. p> Якщо модуль - число складене, то порівняння n-го ступеня може мати і більш n рішень, при цьому коефіцієнти многочлена не зобов'язані бути КРАН р.
Всяке нетривіальне порівняння за mod p рівносильне порівнянні ступеня не вище р-1 і має не більше р-1 рішень.
Теорема (Вільсон). Порівняння (р - 1) + 1 0 (mod p) виконується тоді і тільки тоді, коли р - просте число. p> Доказ. Нехай р - просте число. Якщо р = 2, то, очевидно, 1 + 1 0 (mod 2). Якщо р> 2, то розглянемо порівняння
[(х - 1) (х - 1) ... (х - (р - 1))] - (- 1) 0 (mod p).
Ясно, що це порівняння ступеня не вище р - 2, але воно має р - 1 рішення: 1, 2, 3, ..., р - 1, так як при підстановці будь-якого з цих чисел, доданок у квадратних дужках зве...
