* Данный текст распознан в автоматическом режиме, поэтому может содержать ошибки

МЕТОД СРАВНЕНИЙ 287 Полагая х = а находим: r=P(a)=zQ % (mod /?); поэтому мы имеем тождественно Р(х)—(х — a)Q(x) (mod/0. что и требовалось доказать. Если, кроме решения х = а (mod/?), сравнение (11) имеет ещё отличное от него решение x = b (mod/?), то, полагая в сравнении (12)х=Ь, мы находим: (b — a)Q(b) = 0 (mod/?); но b — а не делится на d, так как b по условию есть решение сравнения (11), отличное от а; следовательно, Q(b) = 0 (mod/?), т. е x=b (mod/?) есть решение сравнения а значит, в силу теоремы 6 тождественна Q(x)==(x — b)RXx) (mod/?), где R(x)—многочлен степени я — 2 с целыми Из (12) и (13) следует тождественно P(x)zn(x — а)(х — b)R(x) Q(x) = 0 (mod??), (13) коэффициентами. (mod/?). Продолжая этот процесс, мы, очевидно, приходим к следующему общему выводу: если сравнение (11) имеет к^п различных решений x=x (mod/?)(l ^ i * ^ £), то имеет место тождественное сравнение t Р(х) = (х — х )(х г — дг ) . . . (х — x )L(x) 2 k (mod/?), где L (х) — многочлен степени п — k с целыми коэффициентами. Заметим, кстати, что коэффициенты старших членов в многочленах Р{х), Q(x) R(x) и L(x) все равны а , ибо каждый из этих мно­ гочленов есть частное от деления предыдущего многочлена на дву­ член вида х — а. Этот результат немедленно приводит к следую­ щему важному выводу: Т е о р е м а 7. Сравнение степени п по простому модулю не может иметь более п решений. В самом деле, если бы сравнение (11) имело п-\-1 различных решений x=Xg (mod/?)(l ^t^n-\-1), то в силу только что про­ веденного общего рассуждения мы, полагая k=n, имели бы тож­ дественно: Р(х) = а (х — Xi)(x—x ) . . . (х—х ) (mod/?). f 0 0 q п Полагая здесь х=х мы нашли бы: а X п+1 и пользуясь тем, что P(x )~0 n+1 Х Х Х m o d (mod/?), Р)> 0 (*n+l — i) ( п+1 — • * • ) " • ( *Ы — п) = ° (