многочлены над полем R, нод и нок.

[sokolix]

многочлены $f(x)=x^6-1$ и $g(x)=x^4-1$
записать в каноническом виде над полем R и найти их НОД и НОК

сам виноват что пропустил, но что то совсем никак , где можно прочитать как решить такую задачу ?
и, сами многочлены уже в каноническом виде ?

[Sonic86]

В Вашем случае можно просто разложить многочлены на множители и найти их $\text{НОД}$ и $\text{НОК}$.
Под каноническим видом, видимо, подразумевалось представление в виде $\sum\limits_{k=1}^n a_kx^k$

[bnovikov]

Надо не разлагать на множители (что не всегда возможно!), а применить алгоритм Евклида.

[Joker_vD]

(Оффтоп)

bnovikov в сообщении #482661 писал(а):

Надо не разлагать на множители (что не всегда возможно!), а применить алгоритм Евклида.

Хочу заметить, что если разложение на множители не всегда возможно, то и алгоритм Евклида не работает. Всякое факториальное кольцо — евклидово, знаете ли.

[Oleg Zubelevich]

Теорема Лагранжа, группа корней из единицы. И рассмотрите сразу $x^n-1,\quad x^m-1$ Это ксательно НОД и НОК

[bnovikov]

Joker_vD в сообщении #482663 писал(а):

Хочу заметить, что если разложение на множители не всегда возможно, то и алгоритм Евклида не работает. Всякое факториальное кольцо — евклидово, знаете ли.

Спасибо за просвещение. А я всегда считал, что наоборот: всякое евклидово кольцо — факториально.

Просветите, уважаемый, еще: поле $R$, оно как - факториально или евклидово?

[VAL]

bnovikov в сообщении #482661 писал(а):

Надо не разлагать на множители (что не всегда возможно!), а применить алгоритм Евклида.

Не вдаваясь в тонкости про евклидовость и факториальность (слава Богу, $\mathbb{R}[x]$ факториально и евклидово), замечу, что алгоритм Евклида далеко не всегда лучше разложения на множители при нахождении НОД.

Например, $f(x)=x^{1000}-1, \ g(x) = (x^2-1)^{498}$.
Можно, конечно, разложить второй многочлен по формуле бинома, а потом применить алгоритм Евклида. Но мне почему-то кажется, что лучше решать по-другому

[nnosipov]

Sonic86 в сообщении #482639 писал(а):

Под каноническим видом, видимо, подразумевалось представление в виде $\sum\limits_{k=1}^n a_kx^k$

Полагаю, здесь речь идёт о каноническом разложении (т.е. разложении на неприводимые над заданным полем сомножители). Теоретически оно всегда есть, а практически его добыть --- нетривиально даже в случае поля рациональных чисел (алгоритм Берлекэмпа). А алгоритм Евклида прост и надёжен. Впрочем, для конкретного примера ТС можно применить много чего (те же круговые многочлены, например), уж очень этот пример специфичен. Только зачем, когда и так всё ясно.

-- Вт сен 13, 2011 21:13:15 --

VAL в сообщении #482684 писал(а):

Например, $f(x)=x^{1000}-1, \ g(x) = (x^2-1)^{498}$.

А что будет, если взять два случайных многочлена 1000-й степени?

[sokolix]

Спасибо всем участникам за помощь.

[VAL]

nnosipov в сообщении #482688 писал(а):

VAL в сообщении #482684 писал(а):

Например, $f(x)=x^{1000}-1, \ g(x) = (x^2-1)^{498}$.

А что будет, если взять два случайных многочлена 1000-й степени?

Вот мне эти случайно и попались

[nnosipov]

VAL, всё гораздо проще: два случайных многочлена будут взаимно просты с вероятностью очень близкой к 1.

[Joker_vD]

bnovikov в сообщении #482668 писал(а):

А я всегда считал, что наоборот: всякое евклидово кольцо — факториально.

Извините, опечатался. В любом случае, разложение на множители применимо в более широком классе колец, чем алгоритм Евклида.

bnovikov в сообщении #482668 писал(а):

поле $R$, оно как - факториально или евклидово?

Евклидово. И, следовательно, факториально.

[Sonic86]

nnosipov в сообщении #482707 писал(а):

VAL, всё гораздо проще: два случайных многочлена будут взаимно просты с вероятностью очень близкой к 1.

Даже равной 1