7.415.
и при
достигается равенство.
7.416.
, и при
достигается равенство.
7.417.
, и при
достигается равенство.
7.42. Теорема. Для каждого
7.43. Теорема. Если
— произвольные многочлены, удовлетворяющие условиям
a
, то существуют такие многочлены
что
и
7.44. Теорема. Если многочлены о и и взаимно просты, а
то
7.441. Либо
либо
либо оба неравенства выполняются одновременно.
7.442. Если
то
и
Доказательство теоремы 7.41, за исключением утверждений
Эти утверждения доказаны при эвристическом рассмотрении алгоритма. Читатель может провести прямое доказательство, используя индукцию по к.
Доказательство теоремы 7.42. Согласно теореме 7.41,
Перемножив эти сравнения, получим
Деление на
дает
Так как
то
Согласно утверждениям
. В силу теорем 7.414 и 7.417
. Следовательно,
и
Доказательство утверждений 7.414 — 7.417. Если
то
и
Так как
то
Аналогично, если
то
и
. Значит,
Замечание к теореме 7.43. Эта теорема дает общее решение (произвольной степени) сравнения а
Для теорем 7.41 и 7.42 важна взаимная простота многочленов
Следовательно, любой многочлен
может быть представлен в виде
Теорема 7.43 утверждает, что если о и и — решения уравнений
то в формулах
участвуют одни и те же многочлены
Более того, согласно теореме 7.43, степени многочленов
малы.
Доказательство теоремы 7.43. По предположению
Умножение на
с использованием утверждения 7.412 дает
где
Далее, умножив первоначальное сравнение на ввиду утверждения 7.413, получим, что
где
Из (7.45) и (7.46) получаем
что, в силу теоремы 7.42, приводит к равенству
Аналогично, из (7-45) и (7.46) получаем
Используя теорему 7.42, приходим к равенству
Доказательство теоремы 7.44. Утверждение 7.441 следует непосредственно из уравнения (7.46) и утверждений 7.415 и 7.417. Значит, если
то
и если
то достигается строгое неравенство. В силу теорем 7.414 и 7.416
Так как
то отсюда следует, что
При этом по теореме
и
Так как по предположению многочлены а и и взаимно просты, то