Схема Горнера для многочлена с целыми коэффициентами

[lamo]

Помогите разобраться, а то голова уже совсем не варит.
Дан многочлен с целыми коэффициентами $P_n(x)=a_nx^n+a_{n-1}x^{n-1}+...+a_1x+a_0, a_i\in \mathbb{Z}$
Пусть имеется рациональный корень $c: P(c)=0, c\in\mathbb{Q}$
Тогда по теореме Безу $P_n(x)=(x-c)Q_{n-1}(x)$, где
$Q_{n-1}(x)=b_{n-1}x^{n-1}+b_{n-2}x^{n-2}+...+b_1x+b_0$
Собственно вопрос: правда ли, что $\forall b_i\in\mathbb{Z}$?
Мне кажется это почти очевидным, но строго доказать это я не могу.
Пусть $c=\frac{p}{q}, p\in\mathbb{Z}, q\in\mathbb{N}, q \neq 1$. Тогда применим схему Горнера для деления исходного многочлена на $(x-c)$. Если на каком-то шаге $b_k\in\mathbb{Q}$, то числитель $b_k$ будет вида $q^m (m \in\mathbb{N})$. И тогда $\forall i\leqslant k: b_k\in\mathbb{Q}$. А это значит, что $r = b_0c+a_0$ не будет равен нулю, т.к. перемножение двух дробей (не нулевых) с одинаковыми основаниями знаменателей и сложение с натуральным числом не даст 0. А значит противоречие, что $c$ - корень.
Похоже на правду?

[VAL]

lamo в сообщении #510268 писал(а):

Помогите разобраться, а то голова уже совсем не варит.
Дан многочлен с целыми коэффициентами $P_n(x)=a_nx^n+a_{n-1}x^{n-1}+...+a_1x+a_0, a_i\in \mathbb{Z}$
Пусть имеется рациональный корень $c: P(c)=0, c\in\mathbb{Q}$
Тогда по теореме Безу $P_n(x)=(x-c)Q_{n-1}(x)$, где
$Q_{n-1}(x)=b_{n-1}x^{n-1}+b_{n-2}x^{n-2}+...+b_1x+b_0$
Собственно вопрос: правда ли, что $\forall b_i\in\mathbb{Z}$?
Мне кажется это почти очевидным, но строго доказать это я не могу.

А мне кажется, что схема Горнера тут не причем.
Достаточно учесть. что $qx-p$ делит $P_n(x)$ в кольце $\mathbb{Z}[x]$.
Или это считается неизвестным?

[lamo]

VAL в сообщении #510297 писал(а):

А мне кажется, что схема Горнера тут не причем.
Достаточно учесть. что $qx-p$ делит $P_n(x)$ в кольце $\mathbb{Z}[x]$.
Или это считается неизвестным?

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

[ewert]

lamo в сообщении #510268 писал(а):

Собственно вопрос: правда ли, что $\forall b_i\in\mathbb{Z}$?
Мне кажется это почти очевидным, но строго доказать это я не могу.

Правдой является даже более сильное утверждение: если несократимая дробь $\frac{p}q$ есть корень многочлена $a_0x^n+a_1x^{n-1}+\ldots+\ldots a_{n-1}x+a_n$, то частное от деления $\frac{a_0x^n+a_1x^{n-1}+\ldots+\ldots a_{n-1}x+a_n}{qx-p}$ есть многочлен с именно целыми коэффициентами.

Причина проста. Поскольку, как известно, знаменатель $q$ долен быть делителем коэффициента $a_0$, эту дробь можно представить как $b_0x^{n-1}+\frac{\widetilde a_1x^{n-1}+a_2x^{n-2}+\ldots+\ldots a_{n-1}x+a_n}{qx-p}$, где $b_0=\frac{a_0}{q}$ и $\widetilde a_1=a_1+b_0p$ -- целые, т.е. в числителе стоит многочлен тоже с целыми коэффициентами, и он по-прежнему делится на знаменатель нацело. Тем самым доказан индукционный переход: если утверждение верно для любого многочлена степени $(n-1)$, то оно верно и для любого многочлена степени $n$. Ну а база индукции (например, при $n=1$) тривиальна.

[nnosipov]

На всякий случай более общий факт: если $f(x)$ и $g(x)$ --- многочлены с целыми коэффициентами, причём $f(x)$ делится на $g(x)$ и коэффициенты $g(x)$ взаимно просты, то частное $f(x)/g(x)$ есть многочлен с целыми коэффициентами.

[lamo]

Всем большое спасибо за ответы.
Уточнение, что

ewert в сообщении #517158 писал(а):

несократимая дробь $\frac{p}q$

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

[ewert]

(Оффтоп)

lamo в сообщении #517272 писал(а):

Просто я пишу программу, которая находит рациональные корни многочлена с целыми коэффициентами.

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

[lamo]

(Оффтоп)

ewert в сообщении #517346 писал(а):

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

Подразумевается, что уже есть готовый многочлен и надо проверить, какие у него рациональные корни. Я понимаю, что среди всех многочленов тех, которые имеют хотя бы один рациональный корень, очень мало. Но задание не я придумывал. Ну а написать программу, которая по введённым корням генерировала бы многочлен для тестовых данных - идея хорошая.

[ewert]

(Оффтоп)

lamo в сообщении #517353 писал(а):

Ну а написать программу, которая по введённым корням генерировала бы многочлен для тестовых данных - идея хорошая.

Хорошая и даже правильная, но требует отладки. Там потребуются как минимум два критерия отбраковки неудачных вариантов. Во-первых, чтоб не слишком большие коэффициенты: ну допустим, сгенерировали мы что-то типа $2345x^4+7118x^2+234x+1779=0$ -- и что, подсовывать это в качестве задания, да?... Во-вторых, необходимо предусмотреть, чтоб одинаковые варианты если и повторялись, то не слишком часто (ну, скажем, не чаще, чем через 300 вариантов, или хотя бы не чаще чем через 32). Ну там и ещё достаточно много эстетических соображений, вынуждающих прибегать к отбраковкам.

[lamo]

(Оффтоп)

ewert в сообщении #517366 писал(а):

Во-первых, чтоб не слишком большие коэффициенты: ну допустим, сгенерировали мы что-то типа $2345x^4+7118x^2+234x+1779=0$ -- и что, подсовывать это в качестве задания, да?

Мне кажется, возникло между нами недопонимание. Какая разница, какие коэффициенты? Для работоспособности программы главное, чтобы они влезли в числовой тип (в своей я использую 64-битное целое со знаком - это больше 9 триллионов).

ewert в сообщении #517366 писал(а):

Во-вторых, необходимо предусмотреть, чтоб одинаковые варианты если и повторялись, то не слишком часто (ну, скажем, не чаще, чем через 300 вариантов, или хотя бы не чаще чем через 32).

Стандартная функция rand хоть и не идеальна, но думаю за 300 раз не выдаст ни одного одинакового числа.
Хочу напомнить, многочлены решает не человек, а программа. Именно поэтому мне было важно знать про целые коэффициенты после применения схемы Горнера, т.к. это влияло на тип, в котором коэффициенты будут храниться.