Помогите разобраться с делением многочленов над кольцом

[Vassermunshinka]

Здравсвуйте! Прошу помочь разобраться с делением многочленов над кольцом $R$(произвольным).
А именно, доказать следующее утверждение(точнее, разобраться с доказательством, используя подсказки из учебника):

Цитата:

Допустим, $g(x), f(x) \in R[x], deg \ g(x) = n, deg \ f(x) = d, f(x) = x^d + \sum\limits_{i=0}^{i=d-1} b_i x^i$(то есть многочлен $f(x)$ приведён). Доказать, что существуют такие многочлены $q(x)$ и $r(x)$, $deg \ r(x) < deg \ f(x) = d$, что

$g(x) = q(x)f(x) + r(x)$

Автор говорит про индукцию и даёт подсказку: если $n > d$, то $a_nx^n = a_nx^{n-d}f(x) + h(x)$. Мы получаем, что $deg \ h(x) < deg \ g(x) = n$. Это я понимаю. А что дальше можно сделать? Как именно использовать индукцию?

Другие учебники смотрел( Лэнга, Даммита-Фута и т.д.), там примерно то же самое написано. И на math.stackexchange гуглил, ответы неполные. Именно то, что они оставляют читателю или спрашивающему, я не могу понять.

[DeBill]

Vassermunshinka в сообщении #1129029 писал(а):

А что дальше можно сделать?

А теперь сделайте то же самое с $h(x)$...
Вообще, если что-то непонятно - в общем виде - попробуйте сделать на конкретном , не шибко сложном, примере. Часто это помогает...

[Vassermunshinka]

DeBill в сообщении #1129035 писал(а):

Vassermunshinka в сообщении #1129029 писал(а):

А что дальше можно сделать?

А теперь сделайте то же самое с $h(x)$...
Вообще, если что-то непонятно - в общем виде - попробуйте сделать на конкретном , не шибко сложном, примере. Часто это помогает...

А индукцию как мы используем? Я просто не могу понять идею доказательства, но очень хочется разобраться.

[DeBill]

"И так далее" - это и есть индукция.
Ну, если хотите аккуратно, то рассуждение должно быть таким:
Предположим, что мы уже умеем делить с остатком все многочлены степени не больше $n$. Далее - Ваше рассуждение. Далее: а поскольку степень $h$ меньше $n$, то, по предположению индукции, $h$ можно поделить с остатком. Тогда ....

[Vassermunshinka]

DeBill в сообщении #1129048 писал(а):

"И так далее" - это и есть индукция.
Ну, если хотите аккуратно, то рассуждение должно быть таким:
Предположим, что мы уже умеем делить с остатком все многочлены степени не больше $n$. Далее - Ваше рассуждение. Далее: а поскольку степень $h$ меньше $n$, то, по предположению индукции, $h$ можно поделить с остатком. Тогда ....

Здорово!

Проверим для $k = 1$. $a_1x = a_1x + 0$, где $q(x) = a_1, f(x) = x, r(x) = 0, deg \ r(x) = -1/ -\infty < 1 = deg \ f(x)$

Тогда получаем, что

$a_nx^n = (a_nx^{n-d}+q(x))f(x) + r(x), deg \ r(x) < deg \ f(x)$.

Это мы доказали для всех одночленов $a_nx^n$. Как обощить доказательство на произвольный многочлен?

[DeBill]

Применим к каждому одночлену...
Или: те же рассуждения проходят и не только для одночленов...

[Vassermunshinka]

Ещё подумал на эту тему. Индукция(сильная) работает так: мы доказываем, что если утверждение верно для всех $k < n$, то оно верно и для $n$( предварительно проверяя для какого-то малого $k$).

Итак, рассматриваем случай, где $deg \ g(x) = d \leq n = deg \ f(x)$. Проверяем для $n = 1$. Верно.

Предполагаем теперь, что утверждение верно для всех многочленов степени $n$ меньше $k$. Для $n = k$ имеем:

$a_kx^k = a_kx^{k-d}f(x) + h(x), deg \ h(x) < k$. Тогда $h(x) = q(x)f(x) + r(x), deg \ f(x) > deg \ r(x)$, и, следовательно,$a_kx^k = (a_kx^{k-d} + q(x))f(x) + r(x), def \ r(x) < deg \ f(x)$.
Теперь рассмотрим многочлен $g(x) - a_kx^k$. $deg(g(x) - a_kx^k) < k$, но мы же не знаем, вдруг $deg(g(x) - a_kx^k) < deg \ f(x) = d$, а мы же рассматриваем только те пары многочленов, где $d \leq n$. Как быть?

[DeBill]

Vassermunshinka в сообщении #1129068 писал(а):

вдруг $deg(g(x) - a_kx^k) < deg \ f(x) = d$,

А это и значит, что все уже поделилось, процесс закончился.

[Vassermunshinka]

Ага! Если $deg(g(x) - a_kx^k) < deg \ f(x)$, то прибавляем к обеим частям равенства $g(x) - a_kx^k$, и получаем:

$g(x) = (a_kx^{k-d} + q(x))f(x) + r(x) + g(x) - a_kx^k, deg \ r(x) < d, deg(g(x) - a_kx^k) < d$, но тогда и $deg(t(x) = r(x) + g(x) - a_kx^k) < d$, и все выполняется.

Если же $deg(g(x) - a_kx^k) \geq deg \ f(x) = d$, то по гипотезе индукции получаем, что $g(x) - a_kx^k = q_1(x)f(x) + r_1(x), deg \ r_1(x) < deg \ f(x) = d$. Прибавляя, получаем:

$f(x) = (a_kx^{k-d} + q(x) + q_1(x))f(x) + r(x) + r_1(x), deg \ r(x) < d, deg \ r_1(x) < d$, но тогда и $deg(r(x) + r_1(x)) < d$. И снова верно.

Таким образом, доказательство по индукции завершено для случая, где $n \geq d$. Мы доказали, что если верно для всех $n < k$, то верно и для $n = k$.

Правильно?

[DeBill]

!