2.3*. Деление многочленов с остатком. Алгоритм Евклида
📏Из жизниДеление многочленов «уголком» устроено ровно как деление чисел: $47$ на $5$ даёт частное $9$ и остаток $2$, потому что $47=9\cdot5+2$, а остаток $2$ меньше делителя $5$. С многочленами то же самое, только вместо «меньше числа» — «меньше по степени».
Деление с остатком
Многочлен $a_nx^n+a_{n-1}x^{n-1}+\ldots+a_1x+a_0$ ($a_n\ne0$) называют многочленом степени $n$; $a_n$ — коэффициент при старшем члене, $a_0$ — свободный член.
🔑ОпределениеРазделить многочлен $A$ на многочлен $B$ с остатком — значит найти многочлены $Q$ (частное) и $R$ (остаток), такие что $A=Q\cdot B+R$, причём степень $R$ меньше степени $B$, либо $R$ — нулевой многочлен. Если $R$ нулевой, говорят, что $A$ делится на $B$ нацело.
Частное $2x^2+3x+9$, остаток $17x-4$ — его степень ($1$) меньше степени делителя $x^2-3x+1$ (степень $2$), значит деление выполнено верно.
А вот $x^5-7x^3-12x+18$ делится на $x^3-2x^2-6$ нацело: частное $x^2+2x-3$, остаток $0$.
Алгоритм Евклида для многочленов
🔑ОпределениеНОД$(A,B)$ — многочлен наибольшей степени, на который делятся нацело оба многочлена $A$ и $B$.
Если $A$ не делится на $B$ нацело, последовательно делят с остатком: $A=Q_1B+R_1$, $B=Q_2R_1+R_2$, $R_1=Q_3R_2+R_3$, ... — пока не получат нулевой остаток. Последний ненулевой остаток и есть НОД$(A,B)$. Процесс обязательно закончится, так как степени остатков строго убывают с каждым шагом.
Пример: НОД двух кубических многочленов
Справа — пошаговый разбор алгоритма Евклида для $A=x^3+3x^2+3x+2$ и $B=x^3+2x^2+2x+1$: на каждом шаге степень остатка падает, пока не дойдём до нуля.
Запомни
🧠Деление и НОД многочленов
$A=Q\cdot B+R$, где $\deg R<\deg B$ или $R=0$;
если $R=0$ — $A$ делится на $B$ нацело;
алгоритм Евклида — последовательное деление с остатком, НОД — последний ненулевой остаток;
алгоритм всегда конечен: степень остатка строго убывает на каждом шаге.