2014 dxdy logo

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

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




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

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

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

 
 
 
 Re: многочлены над полем R, нод и нок.
Сообщение13.09.2011, 15:06 
Надо не разлагать на множители (что не всегда возможно!), а применить алгоритм Евклида.

 
 
 
 Re: многочлены над полем R, нод и нок.
Сообщение13.09.2011, 15:37 

(Оффтоп)

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

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

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

 
 
 
 Re: многочлены над полем R, нод и нок.
Сообщение13.09.2011, 16:12 
Joker_vD в сообщении #482663 писал(а):
Хочу заметить, что если разложение на множители не всегда возможно, то и алгоритм Евклида не работает. Всякое факториальное кольцо — евклидово, знаете ли.


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

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

 
 
 
 Re: многочлены над полем R, нод и нок.
Сообщение13.09.2011, 16:54 
bnovikov в сообщении #482661 писал(а):
Надо не разлагать на множители (что не всегда возможно!), а применить алгоритм Евклида.
Не вдаваясь в тонкости про евклидовость и факториальность (слава Богу, $\mathbb{R}[x]$ факториально и евклидово), замечу, что алгоритм Евклида далеко не всегда лучше разложения на множители при нахождении НОД.

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

 
 
 
 Re: многочлены над полем R, нод и нок.
Сообщение13.09.2011, 17:06 
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-й степени?

 
 
 
 Re: многочлены над полем R, нод и нок.
Сообщение13.09.2011, 17:15 
Спасибо всем участникам за помощь.

 
 
 
 Re: многочлены над полем R, нод и нок.
Сообщение13.09.2011, 17:37 
nnosipov в сообщении #482688 писал(а):
VAL в сообщении #482684 писал(а):
Например, $f(x)=x^{1000}-1, \ g(x) = (x^2-1)^{498}$.
А что будет, если взять два случайных многочлена 1000-й степени?
Вот мне эти случайно и попались :-)

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

 
 
 
 Re: многочлены над полем R, нод и нок.
Сообщение13.09.2011, 17:57 
bnovikov в сообщении #482668 писал(а):
А я всегда считал, что наоборот: всякое евклидово кольцо — факториально.

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

bnovikov в сообщении #482668 писал(а):
поле $R$, оно как - факториально или евклидово?

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

 
 
 
 Re: многочлены над полем R, нод и нок.
Сообщение13.09.2011, 19:06 
nnosipov в сообщении #482707 писал(а):
VAL, всё гораздо проще: два случайных многочлена будут взаимно просты с вероятностью очень близкой к 1. :D

Даже равной 1 :-)

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


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