Теорема о взаимно простых многочленах

[Odysseus]

goganchic
Я все еще рекомендую вам сначала пройти то же самое, но на примере целых чисел (например см. Калужнин "Введение в общую алгебру", гл.3, параграф 1). Там не будет отвлекающих скобок с аргументами, сами утверждения будут нагляднее, и можно будет поэкспериментировать с простыми примерами.

Но раз вы упорно хотите начать изучать делимость с многочленов - ок. Но тогда хотя бы формулируйте это для себя в более понятных терминах и разбивайте на последовательность простых шагов.

TOTAL в сообщении #1493234 писал(а):

Если бы $f(x)$ и $\varphi(x)\psi(x)$ имели общий делитель, то этот делитель делил бы и $\psi(x)$. Это понятно?

goganchic в сообщении #1493403 писал(а):

А вот это непонятно. Откуда мы делаем такой вывод? Не понимаю как это следует из равенства $f(x)[u(x)\psi(x)] + [\varphi(x)\psi(x)]v(x) = \psi(x)$.

1) Что значит, что у $f(x)$ и $\varphi(x)\psi(x)$ есть общий делитель? Это значит, что есть некий многочлен $g(x)$ на который они оба делятся.
2) Вот и поделите обе части равенства на этот многочлен. Слева поделилось без остатка, значит и справа должно поделиться без остатка,
3) Значит $\psi(x)$ в правой части делится на $g(x)$

[vpb]

Odysseus в сообщении #1493409 писал(а):

см. Калужнин "Введение в общую алгебру", гл.3, параграф 1).

Хороший совет.

[Odysseus]

goganchic в сообщении #1493403 писал(а):

Равенство выглядит как теорема о НОД, но в той теореме в правой части стоит НОД. Можем ли мы сказать, что равенство справедливо не только для наибольшего общего делителя, но и для любого делителя двух многочленов? Думаю, что нет, т.к. $\psi(x)$ не общий делитель $f(x)$ и $\varphi(x)\psi(x)$.

И заодно по поводу этого. То, что вы здесь пишите ("Равенство выглядит как теорема о НОД", "Можем ли мы сказать" и "Думаю...") говорит о том, что, как мне кажется, вы не вполне понимаете теорему о НОД для многочленов.

В первом посте вы сформулировали ее так:

goganchic в сообщении #1493403 писал(а):

Если $d(x)$ есть наибольший общий делитель многочленов $f(x)$ и $g(x)$, то можно найти такие многочлены $u(x)$ и $v(x)$, что $f(x)u(x) + g(x)v(x) = d(x)$

и потом вы пишите.

goganchic в сообщении #1492545 писал(а):

В теореме говорится о необходимости, но не достаточности, т.е. автор не говорит, что в случае возможности найти $u(x)$ и $v(x)$ многочлен $d(x)$ будет максимальным общим делителем (или хоть каким-то делителем) для $f(x)$ и $g(x)$.

У Куроша в "Курсе высшей алгебры" (ИМХО не лучший учебник, но сейчас об этом не будем) в самом деле данная формулировка начинается с "Если $d(x)$ есть наибольший общий делитель..." Но если вы посмотрите у него выше алгоритм Евклида, то там как раз и доказывается, что у любых двух многочленов всегда есть НОД. Т.е. там просто не очень удачно сформулирована итоговая теорема о НОД. Лучше было бы "Для любых $f(x)$ и $g(x)$ можно найти такие $u(x)$ и $v(x)$, что $f(x)u(x) + g(x)v(x) = d(x)$ будет НОД $f(x)$ и $g(x)$" и тогда сразу бы покрывались оба утверждения: и о наличии НОД и о том, как его можно выразить через $f(x)$ и $g(x)$.

И далее давайте тоже пройдем по последовательным простым шагам:

1) Очевидно, что в равенстве $f(x)u(x) + g(x)v(x) = d(x)$ при неких произвольных $u(x)$ и $v(x)$ многочлен $d(x)$ совсем не обязан быть не только НОД, но и просто общим делителем $f(x)$ и $g(x)$. Можно же умножить обе части на какой-то многочлен, который не будет делителем $f(x)$ и $g(x)$, и тогда то, что получится справа - заведомо не будет делителем $f(x)$ и $g(x)$. Все что мы можем сказать о $d(x)$ в общей ситуации это то, что он делится на все общие делители $f(x)$ и $g(x)$. (Левая часть на них делится без остатка, значит и правая часть должна делиться без остатка).

2) НО ПРИ ЭТОМ если в $f(x)u(x) + g(x)v(x) = d(x)$ при каких-то $u(x)$ и $v(x)$ вдруг оказалось, что $d(x)$ является общим делителем $f(x)$ и $g(x)$, то он будет их НОД. Мы же п.1 выяснили, что он делится на все другие общие делители $f(x)$ и $g(x)$, а значит это и есть НОД по самому определению НОД.

Значит ни для каких других делителей $d(x)$ многочленов $f(x)$ и $g(x)$ кроме НОД равенства $f(x)u(x) + g(x)v(x) = d(x)$ быть не может.

Обратите внимание, что в п.1 и п.2 теорема о НОД никак не используется. Это все было бы верно, даже если бы мы про нее ничего не знали. Но ее польза состоит в том, что, как оказывается, можно подобрать такие $u(x)$ и $v(x)$, что $f(x)u(x) + g(x)v(x)$ будет НОД для $f(x)$ и $g(x)$

3) А теперь уже используем НОД в отношении ситуации для взаимно простых многочленов:
- Для взаимно простых $f(x)$ и $g(x)$ можно подобрать такие $u(x)$ и $v(x)$, что $f(x)u(x) + g(x)v(x)=1$ (где под $1$ понимается многочлен нулевой степени)
- При этом из п. 1 и 2 мы выяснили, что в этой ситуации никакие другие многочлены в правой части не будут НОД.
- Вот так и получаем, что равенство $f(x)u(x) + g(x)v(x) = 1$, при некоторых $u(x)$ и $v(x)$ может быть тогда и только тогда, когда $f(x)$ и $g(x)$ взаимно просты.

[TOTAL]

Odysseus в сообщении #1493451 писал(а):

Но если вы посмотрите у него выше алгоритм Евклида, то там как раз и доказывается, что у любых двух многочленов всегда есть НОД.

Существование НОД доказывать не надо, НОД есть по определению, что-то просто назвали НОД.

[Odysseus]

TOTAL
А это смотря как его определять. Для целых чисел можно сказать "наибольший" в буквальном смысле слова согласно отношению порядка на множестве целых чисел. Тогда он всегда существует. Но не во всех же кольцах есть отношение порядка. Поэтому лучше его определять как делитель, который делится на все остальные общие делители данных элементов кольца (как и делается в том же Куроше о котором выше идет речь, а также в Калужнине и т.д.), и в этом случае алгоритмом Евклида приходится доказывать его наличие (и поэтому он и существует только в евклидовых кольцах).

[nnosipov]

Odysseus в сообщении #1493455 писал(а):

и поэтому он и существует только в евклидовых кольцах

Не только. Например, НОД существует в любом факториальном кольце.

[Odysseus]

nnosipov Да, поторопился.

[TOTAL]

Odysseus в сообщении #1493455 писал(а):

Поэтому лучше его определять как делитель, который делится на все остальные общие делители данных элементов кольца (как и делается в том же Куроше о котором выше идет речь, а также в Калужнине и т.д.), и в этом случае алгоритмом Евклида приходится доказывать его наличие

Алгоритмом Евклида доказывают существование делителя, который делится на все остальные общие делители данных элементов. Такой делитель затем называют НОД.

[Odysseus]

TOTAL в сообщении #1493462 писал(а):

Алгоритмом Евклида доказывают существование делителя, который делится на все остальные общие делители данных элементов. Такой делитель затем называют НОД.

Для меня это какая-то странная логика и игра слов. Если наличие некого объекта не постулируется (множество, группа и т.д.), то сначала ему дается определение, а потом доказывается его существование внутри некоей структуры. Может в каких-то случаях и бывают исключения, но с НОД стандартный способ именно таков. Иначе про что угодно можно сказать "Существование X доказывать не надо, X есть по определению, что-то просто назвали X", а обосновывать это тем, что сначала это "доказывается", а потом "называется". Ну и в любом случае, доказывать наличие НОД в кольце многочленов нужно, а именно про это я и писал выше.

[goganchic]

Odysseus в сообщении #1493451 писал(а):

1) Очевидно, что в равенстве $f(x)u(x) + g(x)v(x) = d(x)$ при неких произвольных $u(x)$ и $v(x)$ многочлен $d(x)$ совсем не обязан быть не только НОД, но и просто общим делителем $f(x)$ и $g(x)$. Можно же умножить обе части на какой-то многочлен, который не будет делителем $f(x)$ и $g(x)$, и тогда то, что получится справа - заведомо не будет делителем $f(x)$ и $g(x)$. Все что мы можем сказать о $d(x)$ в общей ситуации это то, что он делится на все общие делители $f(x)$ и $g(x)$. (Левая часть на них делится без остатка, значит и правая часть должна делиться без остатка).

Огромное спасибо за объяснение! Вот этого параграфа мне как раз и не хватало. Вроде утверждение простое и очевидное, но оно ускользало от меня.