Нахождение остатка от деления многочлена

[e7e5]

Решал такую задачку:
Найти частное $T(x)$ и остаток $R(x)$ от деления многочлена
$P(x)=x^{30}-1$ на многочлен $Q(x)=x^5+1$

Задачку решил обычным делением одного многочлена на другой столбиком.
Остаток получился равным нулю,
$T(x)=x^{25}-x^{20}+x^{15}-x^{10}+x^5-1$

Возник вопрос - есть ли другой способ нахождения ( оценки) остатка от деления, когда многочлены больших степеней ( делить столбиком - бумаги не хватит, и пальчики писать устают)?

[Dandan]

$T(x)=(x^5-1)(x^{20}+x^{10}+1)$

[VAL]

Dandan писал(а):

$T(x)=(x^5-1)(x^{20}+x^{10}+1)$

Точнее, $T(x)=(x^{10}-1)(x^{20}+x^{10}+1)$

[e7e5]

VAL писал(а):

Dandan писал(а):

$T(x)=(x^5-1)(x^{20}+x^{10}+1)$

Точнее, $T(x)=(x^{10}-1)(x^{20}+x^{10}+1)$

Спасибо, но, вроде, мой вопрос был про нахождение ( оценку) остатка от деления.
Т.е. в заданном примере $R(x)=0$, а вот для какого-нибудь др. многочлена, как найти
$R(x)$, не прибегая к делению уголком?
Есть ли иные методы?

[ewert]

Ну, есть ещё теорема Безу в сочетании с заменой переменной (для случаев, аналогичных этому).

[e7e5]

ewert писал(а):

Ну, есть ещё теорема Безу в сочетании с заменой переменной (для случаев, аналогичных этому).

А если замена переменных и т. Безу не поможет?
Например, если нужно оценить остаток
$x^{30}-1$ деления на $x^2+x+1$

[gefest_md]

e7e5 писал(а):

как найти
$R(x)$, не прибегая к делению уголком?
Есть ли иные методы?

Равенству $x^{30}-1=(x^5+1)(x^{25}-x^{20}+x^{15}-x^{10}+x^{5}-1)$ можно поставить в соответствие таблицу, в которой первая колонка даёт коэфициенты частного, а последний ряд - остатка.

\begin{tabular}{r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r} &$0$&$0$&$0$&$0$&$-1$&&&&&&&&&&&&&&&&&&&&&&&&&&\\\hline &$1$&$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$&$-1$\\\hline\hline $1$&$0$&$0$&$0$&$0$&$-1$&&&&&&&&&&&&&&&&&&&&&&&&&&\\\hline $0$&$0$&$0$&$0$&$0$&$0$&&&&&&&&&&&&&&&&&&&&&&&&&&\\\hline $0$&$0$&$0$&$0$&$0$&$0$&&&&&&&&&&&&&&&&&&&&&&&&&&\\\hline $0$&$0$&$0$&$0$&$0$&$0$&&&&&&&&&&&&&&&&&&&&&&&&&&\\\hline $0$&$0$&$0$&$0$&$0$&$0$&&&&&&&&&&&&&&&&&&&&&&&&&&\\\hline $-1$&$0$&$0$&$0$&$0$&$1$&&&&&&&&&&&&&&&&&&&&&&&&&&\\\hline $0$&$0$&$0$&$0$&$0$&$0$&&&&&&&&&&&&&&&&&&&&&&&&&&\\\hline $0$&$0$&$0$&$0$&$0$&$0$&&&&&&&&&&&&&&&&&&&&&&&&&&\\\hline $0$&$0$&$0$&$0$&$0$&$0$&&&&&&&&&&&&&&&&&&&&&&&&&&\\\hline $0$&$0$&$0$&$0$&$0$&$0$&&&&&&&&&&&&&&&&&&&&&&&&&&\\\hline $1$&$0$&$0$&$0$&$0$&$-1$&&&&&&&&&&&&&&&&&&&&&&&&&&\\\hline $0$&$0$&$0$&$0$&$0$&$0$&&&&&&&&&&&&&&&&&&&&&&&&&&\\\hline $0$&$0$&$0$&$0$&$0$&$0$&&&&&&&&&&&&&&&&&&&&&&&&&&\\\hline $0$&$0$&$0$&$0$&$0$&$0$&&&&&&&&&&&&&&&&&&&&&&&&&&\\\hline $0$&$0$&$0$&$0$&$0$&$0$&&&&&&&&&&&&&&&&&&&&&&&&&&\\\hline $-1$&$0$&$0$&$0$&$0$&$1$&&&&&&&&&&&&&&&&&&&&&&&&&&\\\hline $0$&$0$&$0$&$0$&$0$&$0$&&&&&&&&&&&&&&&&&&&&&&&&&&\\\hline $0$&$0$&$0$&$0$&$0$&$0$&&&&&&&&&&&&&&&&&&&&&&&&&&\\\hline $0$&$0$&$0$&$0$&$0$&$0$&&&&&&&&&&&&&&&&&&&&&&&&&&\\\hline $0$&$0$&$0$&$0$&$0$&$0$&&&&&&&&&&&&&&&&&&&&&&&&&&\\\hline $1$&$0$&$0$&$0$&$0$&$-1$&&&&&&&&&&&&&&&&&&&&&&&&&&\\\hline $0$&$0$&$0$&$0$&$0$&$0$&&&&&&&&&&&&&&&&&&&&&&&&&&\\\hline $0$&$0$&$0$&$0$&$0$&$0$&&&&&&&&&&&&&&&&&&&&&&&&&&\\\hline $0$&$0$&$0$&$0$&$0$&$0$&&&&&&&&&&&&&&&&&&&&&&&&&&\\\hline $0$&$0$&$0$&$0$&$0$&$0$&&&&&&&&&&&&&&&&&&&&&&&&&&\\\hline $-1$&$0$&$0$&$0$&$0$&$1$&&&&&&&&&&&&&&&&&&&&&&&&&&\\\hline\hline $0$&$0$&$0$&$0$&$0$&&&&&&&&&&&&&&&&&&&&&&&&&&& \end{tabular}

[ewert]

e7e5 писал(а):

А если замена переменных и т. Безу не поможет?
Например, если нужно оценить остаток
$x^{30}-1$ деления на $x^2+x+1$

В общем случае -- никак, любой регулярный метод сведётся к делению уголком, если не учитывать специфику задачи. А, скажем, в последнем случае -- достаточно домножить и разделить на $(x-1)$.