§ 6.4. Вычисление корней

Остается еще один вопрос, который нужно рассмотреть. Существует ли натуральное к, меньшее, чем , при котором для всех целых чисел а, не делящихся на

Можно попытаться ответить на него следующим образом. Хорошо известная теорема алгебры говорит, что полиномиальное уравнение не может иметь корней больше, чем его степень. А поскольку, по предположению, сравнение справедливо для всех целых чисел, взаимно простых с корни полиномиального уравнения это Таким образом, уравнение имеет разных корня. По упомянутой теореме получаем оценку: к Так что ответ на поставленный вопрос отрицателен.

Хотя эти рассуждения корректны, они прячут истинную природу проблемы в теореме, с помощью который мы решили этот вопрос. Когда мы говорим о полиномиальном уравнении, мы обычно имеем ввиду уравнение с вещественными или комплексными коэффициентами. А под «корнем» мы подразумеваем вещественный или комплексный корень. Но коэффициенты

уравнения из нашего рассуждения, как и его корни, суть элементы Вот где собака зарыта! Нам нужно показать, что теорема об оценке числа корней полиномиального уравнения справедлива и в этом случае. Может, это опять неоправданный педантизм? Отнюдь нет. Хотя эта теорема верна в случае простого модуля, для составного модуля она ложна!

Теорема. Пусть многочлен степени к с целыми коэффициентами и старшим коэффициентом 1. Если простое число, то имеет не более к корней в

Прежде чем погрузиться в доказательство, мы должны обратить внимание на два момента. Во-первых, модуль должен быть простым, поскольку нам нужно следующее свойство: если то или или Заметим, что это, фактически, фундаментальное свойство простых чисел, сформулированное на языке сравнений. Во-вторых, мы выделим один моментов доказательства в отдельную лемму, которую докажем в конце этого параграфа.

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

Докажем теорему индукцией по (степени многочлена) с помощью этой леммы. Если то И соответствующее уравнение имеет только одно решение в Итак, многочлен степени 1 имеет единственный корень в и теорема в этом случае верна.

Предположим теперь, что любой многочлен степени к — 1 со старшим коэффициентом 1 имеет не более к — 1 корня в Это предположение индукции. Мы хотим показать, что данное предположение влечет аналогичное утверждение для многочлена степени к со старшим коэффициентом 1.

Итак, пусть многочлен степени к с целыми коэффициентами, старший из которых равен 1. Если не имеет корней в то доказывать нечего, ибо . Такие многочлены в действительности существуют; соответствующий пример приведен после доказательства теоремы. Следовательно, мы можем предполагать, что имеет корень иначе говоря, По лемме

где степень равна . Так как старшие коэффициенты многочленов а равны 1, то же самое справедливо и для многочлена Значит, мы можем применить индуктивное предположение к

Редуцируя равенство (4.1) по модулю мы получаем

Пусть а — еще один корень Это означает, что

Заменяя на а в (4.2), и используя эти сравнения, мы имеем

Так как простое, то это влечет сравнение Мы заключаем, что если корень многочлена отличный от а, то является и корнем Иначе говоря, только на один корень больше чем . А по предположению индукции у последнего многочлена не более, чем различных корней в Следовательно, не может иметь больше к разных корней, что завершает индуктивное доказательство.

Рассмотрим несколько примеров. Первый из них — многочлен Он удовлетворяет всем условиям теоремы,

но не имеет корней по модулю 5. Действительно, единственно возможные вычеты квадратов целых чисел по модулю 5 — это 1 и 4, откуда немедленно следует наше заявление. Это как раз тот пример, о котором упоминалось в доказательстве теоремы.

Второй пример иллюстрирует, что происходит, когда мы пытаемся искать корни многочлена по составному модулю. Корни многочлена это 95, 150, 235 и 290, что легко проверить. Итак, мы представили полиномиальное уравнение степени 2 с четырьмя корнями. Это, конечно, не противоречит нашей теореме, поскольку 385 составное число.

Для завершения доказательства теоремы необходимо проверить лемму. Мы опять будем делать это по индукции. Однако, если попытаться применить принцип индукции в том виде, который сформулирован в § 6.2, мы убедимся, что в доказательстве откроется дырочка. Позже посмотрим, к какой проблеме может привести такое доказательство.

Мы вернемся к лемме, сформулировав принцип индукции в более тонкой форме. Индуктивная гипотеза принципа в форме из § 6.2 предполагает, что верно для некоторого целого к 1. Но практически, когда мы пытаемся доказывать утверждение опираясь на мы уже знаем об истинности Поэтому предположение о справедливости не только но и будет небольшой и естественной модификацией метода. Зато для доказательства мы сможем использовать более полную информацию. Формулировка принципа, включающая это дополнение, выглядит следующим образом.

Принцип математической индукции. Предположим, что для каждого натурального числа сформулировано утверждение обладающее следующими двумя свойствами:

(1) верно;

(2) если верны для натурального к, то утверждение также верно.

Тогда справедливо для всех натуральных

Пользуясь новой формулировкой принципа, лемму теперь можно легко доказать индукцией по степени многочлена Если то для некоторых целых Поэтому

Предположим теперь, что утверждение леммы выполнено для любого многочлена с целыми коэффициентами, степень которого не превосходит Исходя из этого предположения, мы хотим показать, что лемма справедлива для многочлена с целыми коэффициентами степени Пусть

где Обозначим через разность

то

Ясно, что степень многочлена меньше или равна Заметим, однако, что степень будет в точности равна только если но у нас нет способа узнать так это, или нет. Поэтому возможна ситуация, когда степень меньше, чем Это как раз тот момент, когда мы сталкиваемся с трудностями при использовании принципа индукции в форме, сформулированной в § 6.2. Заметим также, для будущих ссылок, что

Так как степень многочлена меньше или равна предположение индукции влечет

где многочлен с целыми коэффициентами, степень которого на единицу меньше, чем степень Ввиду равенства получаем

Но , так что

Наконец, имеет степень в точности потому что степень меньше Это завершает доказательство леммы.

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

причем либо либо его степень меньше степени . Значит, его степень должна быть равной 0, т.е. целое число. Заменим в уравнении на а:

Таким образом, мы можем переписать (4.3) в виде:

что завершает доказательство.

Упражнения

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)