7.4. Алгоритм решения ключевого уравнения над произвольным полем

Первоначально полагаем Далее проводим рекурсию следующим образом. Если не известно, то рекурсия не проводится; в противном случае полагаем равными коэффициенту при в произведении

Если или если или если и то полагаем

Если и если или и то полагаем

7.41. Теорема. Для любого к

7.414. , и равенство достигается при

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

Так как то отсюда следует, что При этом по теореме и Так как по предположению многочлены а и и взаимно просты, то