Деление многочленов с остатком

Математика

Деление многочленов с остатком

В процессе деления одного многочлена на другой результат можно представить в виде суммы.
Для любых многочленовA(x)A(x) и B(x)B(x), при условии, что степень B(x)B(x) больше нуля, справедливо разложение:

A(x)=Q(x)B(x)+R(x),A(x) = Q(x)B(x) + R(x),
где Q(x)Q(x) — частное (неполное), а R(x)R(x) — остаток, причём степень R(x)R(x) меньше степени B(x)B(x).
Если остаток R(x)=0R(x) = 0, говорят, что многочлен A(x)A(x) делится на B(x)B(x) без остатка.

Примеры деления многочленов:

Остаток от деления выражения 2x4+4x3+62x^4 + 4x^3 + 6 на x2+2x^2 + 2 равен −2x+2-2x + 2:
2x4+4x3+6=(2x2+2)(x2+2)−2x+2.2x^4 + 4x^3 + 6 = (2x^2 + 2)(x^2 + 2) - 2x + 2.


Остаток от деления x5+2x4+3x3+4x^5 + 2x^4 + 3x^3 + 4 на x3+1x^3 + 1 равен x2+3x^2 + 3:
x5+2x4+3x3+4=(x2+2)(x3+1)+x2+3.x^5 + 2x^4 + 3x^3 + 4 = (x^2 + 2)(x^3 + 1) + x^2 + 3.


Остаток от деления 3x6+5x4+23x^6 + 5x^4 + 2 на x7+1x^7 + 1 — это сам делимый многочлен:
3x6+5x4+2=0⋅(x7+1)+3x6+5x4+2.3x^6 + 5x^4 + 2 = 0 \cdot (x^7 + 1) + 3x^6 + 5x^4 + 2.


Остаток от деления x3+2x2+x+1x^3 + 2x^2 + x + 1 на x+1x + 1 равен нулю:
x3+2x2+x+1=(x2+1)(x+1)+0.x^3 + 2x^2 + x + 1 = (x^2 + 1)(x + 1) + 0.


Остаток от деления x4+4x3+6x2+8x^4 + 4x^3 + 6x^2 + 8 на x2+2x^2 + 2 тоже равен нулю:
x4+4x3+6x2+8=(x2+2)(x2+2)+0.x^4 + 4x^3 + 6x^2 + 8 = (x^2 + 2)(x^2 + 2) + 0.


Доказательство существования такого представления

Докажем, что для любых многочленов A(x)A(x) и B(x)B(x) (со степенью B(x)>0B(x) > 0) существует представлениевида A(x)=Q(x)B(x)+R(x)A(x) = Q(x)B(x) + R(x), где степень R(x)<deg⁡B(x)R(x) < \deg B(x).

Докажем это по индукции по степени A(x)A(x).
Базис индукции:
если deg⁡A(x)=0\deg A(x) = 0, то есть A(x)A(x) — константа, можно записать:
A(x)=0⋅B(x)+A(x).A(x) = 0 \cdot B(x) + A(x).


Переход:
предположим, что утверждение верно для всех многочленов степени n≤mn \le m, докажем для степени k=n+1k = n + 1.

Случай 1: deg⁡A(x)<deg⁡B(x)\deg A(x) < \deg B(x)Тогда деление не выполняется, и A(x)A(x) записывается так:
A(x)=0⋅B(x)+A(x).A(x) = 0 \cdot B(x) + A(x).


Случай 2: deg⁡A(x)=deg⁡B(x)\deg A(x) = \deg B(x)
Запишем:
A(x)=an+1xn+1+anxn+⋯+a0,\B(x)=bn+1xn+1+bnxn+⋯+b0.A(x) = a_{n+1}x^{n+1} + a_nx^n + \dots + a_0, \B(x) = b_{n+1}x^{n+1} + b_nx^n + \dots + b_0.


Тогда:
A(x)=an+1bn+1B(x)−(an+1bn+1B(x)−A(x)),A(x) = \frac{a_{n+1}}{b_{n+1}}B(x) - \left(\frac{a_{n+1}}{b_{n+1}}B(x) - A(x)\right),

а вычитание в скобках даст многочлен меньшей степени.

Случай 3:
deg⁡A(x)>deg⁡B(x)\deg A(x) > \deg B(x)
Представим A(x)A(x) как:
A(x)=x⋅A’(x),A(x) = x \cdot A’(x),
где A’(x)A’(x) — многочлен меньшей степени.
По предположению индукции:
A’(x)=Q’(x)B(x)+R’(x),A’(x) = Q’(x)B(x) + R’(x),
значит:
A(x)=xA’(x)=x(Q’(x)B(x)+R’(x))=(xQ’(x))B(x)+xR’(x).A(x) = xA’(x) = x(Q’(x)B(x) + R’(x)) = (xQ’(x))B(x) + xR’(x).


Поскольку степень xR’(x)xR’(x) всё ещё меньше степени B(x)B(x), то утверждение доказано. Если хотите, я могу оформить следующий блок аналогично.

Top.Mail.Ru