Пункт 20. Порівняння будь-якого степеня за простим модулем.
У цьому пункті розглянемо порівняння виду f(x) º 0(mod p), де р - просте число, f(x)=axn +a1 xn-1+…+an-многочлен з цілими коефіцієнтами, і навчимося ці порівняння розв’язувати.
Лема 1. Довільне порівняння f(x) º 0(mod p), де р - просте число, рівносильне деякому порівнянню степеня не вищого за p-1.
Доказ. Розділимо f(x) на многочлен xp-x ("многочлен ділення круга") із залишком: f(x)=(xp-x)× Q(x)+R(x), де, як відомо, степінь залишку R(x) не перевищує р-1. Але за теоремою Ферма, xp-xº 0(mod p). Це означає, що f(x)º R(x)(mod p), а вихідне порівняння рівносильне порівнянню R(x)º 0(mod p).
За допомогою доведеної леми можна звести розв’язування порівняння високого степеня до розв’язування порівняння меншого степеня.
Лема 2. Якщо порівняння axn+a1 xn-1+…+anº 0(mod p) степеня n за простим модулем р має більше n різних розв’язків, то всі коефіцієнти a,a1 ,…,an кратні р.
Доказ. Нехай порівняння axn +a1 xn-1+…+anº 0(mod p), має n+1 розв’язок і x1 ,x2 ,…,xn,xn+1–найменші невід’ємні лишки цих розв’язків. Тоді многочлен f(x) представимо у виді:
f(x)=a(x-x 1 )(x-x 2 )…(x-xn-2)(x-xn-1)(x-xn)+
+b(x-x1)(x-x2)…(x-xn-2)(x-xn-1)+
+c(x-x1)(x-x2)…(x-xn-2)+
+…+
+k(x-x1)(x-x2)+
+l(x-x1)+
+m.
Дійсно, коефіцієнт b мусить дорівнювати коефіцієнту при xn-1 у різниці f(x)-a(x-x1 )(x-x2)…(x-xn); коефіцієнт с – це коефіцієнт перед xn-2 у різниці f(x)-a(x-x1 )(x-x2 )…(x-xn)-b(x-x1)(x-x2)…(x-xn-1),і т.д.
Тепер підставимо послідовно x=x1 ,x2 ,…,xn,xn+1... Маємо:
1) f(x1)=m º 0(mod p), отже, р ділить m.
2) f(x2 )=m+l(x2 -x1 ) º l(x2 -x1 )º 0(mod p), отже, р ділить l, тому що р не може поділяти x2 -x1, оскільки x2<p, x1<p.
3) f(x3)º k(x3 -x1 )(x3 -x2 )º 0(mod p), отже, р ділить k. І т.д.
Виходить, що всі коефіцієнти a, b, c,...,k, l кратні р. Це означає, що всі коефіцієнти a,a1,…,an теж кратні р, адже вони є сумами чисел, кратних р. (Переконайтеся в цьому самостійно, розкривши дужки в написаному вище розкладі многочлена f(x) на суми добутків лінійних множників.)
Зверніть увагу на умови простоти модуля порівняння у формулюванні леми 2. Якщо модуль- число складне, то порівняння n-ого степеня може мати більше n розв’язків, при цьому, коефіцієнти многочлена не мусять бути кратними р. Приклад: порівняння другого степеня x2º1(mod 16) має аж цілих чотири різних розв’язки:
xº1(mod 16), xº7(mod 16), xº 9(mod 16), xº15(mod 16).