2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Задача с полиномами ( китайская теорема об остатках)
Сообщение19.03.2009, 12:00 
Аватара пользователя
Определить полином наименьший степени, дающий в остатке $2x$ при делении на $(x-1)^2$ и $3x$ при делении на $(x-2)^3$
собственно что смог сделать это составить систему $\left\{\begin {array} {1}
P(x)=Q(x)(x-1)^2 + 2x,\\
P(x)=G(x)(x-2)^3 + 3x.\end{array}\right$
а так же определить что искомый полином и $(x-1)^2$ взаимнопросты, так же как искомый полином и $(x-2)^3$ ну и из системы видно что $deg P(x) \geqslant 3$, а $deg Q(x) = deg G(x) + 1$. и не могу понять что делать дальше, подскажите чуток :roll:

 
 
 
 
Сообщение19.03.2009, 12:27 
Аватара пользователя
Это китайская теорема об остатках

Там она для целых чисел, но в данном случае многочлены - это то же самое, отличается только механизмом деления с остатком.

Вот здесь явно написано про китайскую теоремы для многочленов http://www.intuit.ru/department/mathematics/compalgebra/8/ (утв. 17.6)

Добавлено спустя 10 минут 42 секунды:

Непосредственно же решить можно, например, так: записываете искомый полином в неопределенными коэффициентами (теорема об остатках подскажет, какую максимальную степень он может иметь). Подставляете в первое Ваше уравнение $x=1$, а во второе - $x=2$, получаете два линейных уравнения на коэффициенты. Затем дифференцируете оба равенства и снова подставляете те же значения - получите еще два уравнения. Ну и второе уравнение можно продифференцировать еще раз и еще раз подставить $x=2$. Этого должно хватить. Из системы линейных уравнений находите коэффициенты искомого полинома.

 
 
 
 
Сообщение19.03.2009, 12:40 
Аватара пользователя
Спасибо за наводку на теорему, в принципе с решением разобрался

 
 
 
 
Сообщение19.03.2009, 13:04 
Удобнее переписать систему в виде

$$\begin{cases}P(t)=Q(t)\cdot(t+1)^2+2t+4,\\P(t)=R(t)\cdot t^3+3t+6\end{cases}$$

(после замены $t=x-2$). В отличие от чисел, остатки для многочленов тупо складываются. При этом:

$(t+1)^2 \mod t^3=t^2+2t+1;$
$t(t+1)^2 \mod t^3=2t^2+t;$
$t^2(t+1)^2 \mod t^3=t^2.$

Отсюда тождество на неопределённые коэффициенты ($Q(t)=A+Bt+Ct^2$):

$A(t^2+2t+1)+B(2t^2+t)+Ct^2+2t+4\equiv3t+6.$

Т.е.:

$\begin{pmatrix}1&2&1\\2&1&0\\1&0&0\end{pmatrix}\cdot\begin{pmatrix}A\\B\\C\end{pmatrix}=\begin{pmatrix}0\\1\\2\end{pmatrix}.$

Очевидно, что многочленом $Q(t)$ меньшей степени при данной правой части, т.е. комбинации остатков в условии, не обойдёшься. Т.е. многочлен $P(x)$ степень меньше четырёх иметь не может, а вот больше или равную -- ради бога.

 
 
 
 
Сообщение19.03.2009, 13:06 
Аватара пользователя
Можно ещё так. Берём одно из двух равенств, например, второе
$P(x)=G(x)(x-2)^3+3x$ и пишем условие, при котором полином $P(x)-2x=G(x)(x-2)^3+x$ делится на $(x-1)^2$.
Это даёт два условия - на $G(1)$ и $G'(1)$

 
 
 
 
Сообщение19.03.2009, 13:13 
Хм. Но нам-то надо ровно три условия.

 
 
 
 
Сообщение19.03.2009, 13:54 
Аватара пользователя
$G(x)$ имеет первую степень, поэтому два условия.

 
 
 
 
Сообщение19.03.2009, 14:02 
Да, это правда. Надо было делить на меньшую степень, т.е. рассматривать

$$\begin{cases}P(t)=Q(t)\cdot t^2+2t+2,\\P(t)=R(t)\cdot(t-1)^3+3t+3.\end{cases}$$

Как-то инстинктивно не захотелось куб разности раскладывать.

 
 
 
 
Сообщение19.03.2009, 15:11 
Аватара пользователя
ewert в сообщении #196594 писал(а):
Как-то инстинктивно не захотелось куб разности раскладывать.

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

 
 
 [ Сообщений: 9 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group