НОД множества чисел

[EminentVictorians]

Пусть $A$ - евклидово кольцо и $a$, $b$ - некоторые его элементы. Для них всегда существует наибольший общий делитель $(a, b)$. А выполняется ли аналогичное утверждение для 3-ех элементов $a , b , c$? Я думаю, что да.

Пусть $P_1$ - множество общих делителей $a$ и $b$, $P_2$ - множество общих делителей $b$ и $c$, $P_3$ - множество общих делителей $a$, $b$ и $c$.
1. $P_1$ совпадает с множеством делителей $(a, b)$. Аналогично $P_2$ совпадает с множеством делителей $(b, c)$.
2. Очевидно, $P_3 = P_1 \cap P_2$
3. Теперь посмотрим на $((a,b) , (b, c))$. Во первых, $((a,b) , (b, c)) \in P_3$, а во-вторых он делится на любой общий делитель $(a, b)$ и $(b, c)$, т.е. он делится на любой элемент из $P_3$, а значит является наибольшим общим делителем элементов $a$, $b$ и $c$, что и требовалось доказать.

Рассуждая аналогично, получаем справедливость утверждения не только для 3-ех элементов, но и для любого $n$.

А корректно ли говорить о НОД произвольного множества чисел? Ведь общий делитель (единица) есть у любого множества чисел из $A$ (хоть несчетного). Если вдруг среди общих делителей нашелся тот, который делится на все остальные, то он и будет НОД-ом этого множества чисел. Вроде все нормально определяется.

Меня интересуют 2 вопроса.
1. Рассматривается ли где-нибудь такая конструкция НОД-а для произвольного множества чисел?
2. Как обстоят дела с существованием такого НОД-а для произвольного множества чисел.

[Dmitriy40]

А разве это не доказывается легко по индукции? НОД двух чисел принадлежит тому же множеству, а значит можно заменить $(a,b,c)$ на $((a,b),c)$. Повторяя шаг добавления нового числа пройдём по всему множеству.

ВольфрамАльфа вполне позволяет запись $\gcd(a,b,c,d)$.

[EminentVictorians]

Dmitriy40 в сообщении #1507016 писал(а):

пройдём по всему множеству.

А если множество несчетное? И даже если счетное, не очень понятно Ваше рассуждение. Насколько я понял, Вы предлагаете рассмотреть последовательность $n \to gcd(a_1, ... ,a_n)$. А что с ней делать дальше?

Dmitriy40 в сообщении #1507016 писал(а):

ВольфрамАльфа вполне позволяет запись
$\gcd(a,b,c,d)$.

Я не отрицаю возможность корректного определения и существования НОД-а для конечного набора из $n$ чисел. Но ведь набор может быть и бесконечным (и даже несчетным).

[ИСН]

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

[EminentVictorians]

ИСН в сообщении #1507022 писал(а):

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

В случае НОД-а видимо даже ухищрений никаких не требуется. НОД-ом множества чисел будем называть их общий делитель, делящийся на любой их общий делитель. Я думаю тут все вполне корректно. Мне бы с существованием разобраться...

[kotenok gav]

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

[ИСН]

Ухищрение требуется, но банальное: "НОДом бесконечного множества будем называть предел последовательности НОДов таких-то конечных множеств при..."
Существование обеспечивается тем, что последовательность монотонна и ограничена, например.

[nnosipov]

ИСН в сообщении #1507097 писал(а):

Ухищрение требуется, но банальное

Еще банальнее было бы рассмотреть идеал, порожденный данным бесконечным множеством.

[EminentVictorians]

ИСН в сообщении #1507097 писал(а):

Существование обеспечивается тем, что последовательность монотонна и ограничена, например.

Вы структуру порядка на $\mathbb{Z}$ используете. А у меня просто евклидово кольцо.

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

Еще банальнее было бы рассмотреть идеал, порожденный данным бесконечным множеством.

Я немного знаю, что такое идеал, но у Винберга они позже идут. Допустим, я рассмотрел идеал, порожденный этим бесконечным множеством. Что с ним делать дальше?

[nnosipov]

EminentVictorians в сообщении #1507103 писал(а):

Что с ним делать дальше?

Осознать, что он главный. Можно пока отложить вопрос --- хотя бы до темы "Кольца главных идеалов" (каковыми евклидовы кольца, безусловно, являются).

[EminentVictorians]

Возник еще один вопрос, теперь по поводу НОК.

Надо доказать, что в евклидовом кольце $A$ для любых двух элементов $a$ и $b$ из $A$ существует $[a, b]$. (квадратные скобки обозначают НОК).

Я решил доказать вот как. Пусть для начала $a$ и $b$ оба необратимые ненулевые. Остальные случаи тривиальны.

Рассмотрим какие-нибудь разложения $a = p_1 \cdot ... \cdot p_n$ и $b = q_1 \cdot ... \cdot q_m$ на простые множители. Положим $P_0 = p_1 \cdot ... \cdot p_n$ и $S_0 = p_1 \cdot ... \cdot p_n$. На первом шаге делаем следующее: если среди $p_i$ из разложения $P_0$ найдется $p_i$, делящийся на $q_1$, то положим $P_1 = \frac{P_0}{p_i}$, $S_1 = p_1 \cdot ... \cdot p_n$. Если же среди $p_i$ из разложения $P_0$ никакой $p_i$ не делится на $q_1$, то положим $P_1 = P_0$, $S_1 = S_0 \cdot q_1$. Далее переходим ко второму шагу и аналогично рассматриваем $q_2$. И т.д. Далее возможны 2 варианта. Либо мы таким образом благополучно дойдем до $m$-ного шага и получим некий $S_m$ по итогу, либо на некотором шаге с номером $k < m$ окажется так, что $P_k = 1$. Тогда на $k+1$-ом шаге просто домножаем $S_k$ на $q_{k+1} \cdot ... \cdot q_m$, т.е. $S_{k+1} = s_1 \cdot ... \cdot s_k \cdot q_{k+1} \cdot ... \cdot q_m$ (где $s_i$ ($1 \leqslant i \leqslant k$) - это элементы произведения $S_k$ после завершения $k$-ого шага).


Понятно, что последняя $S$, которую мы получим, и будет искомым НОК($a$, $b$). Но я хочу это строго доказать. А именно надо доказать, что последняя $S$ делит любое общее кратное $a$ и $b$. Я примерно понимаю, как это сделать, но получается как-то сложно. Пусть $d$ - общее кратное $a$ и $b$. Разложим его как-нибудь на простые множители $d = d_1 \cdot ... \cdot d_z$. Раз $d$ делится на $a$, то существует $\varphi$ такое, что $d = a \cdot \varphi$. Разложение $a$ на простые множители у нас есть: $a = p_1 \cdot ... \cdot p_n$. Это разложение не обязано входить как подстрока в произведение $d = d_1 \cdot ... \cdot d_z$, но эти $d_i$-ые можно перегруппировать так, что первые $n$ из них будут соответственно попарно ассоциированы с $a_i$-ыми. Короче говоря, среди $d = d_1 \cdot ... \cdot d_z$ можно выделить 2 подстроки: одна попарно ассоциирована с разложением $a$, другая - попарно ассоциирована с разложением $b$. И эти подстроки могут пересекаться. Надо доказать, что $S$ будет делить "объединение" этих подстрок. Вот с этим и проблема. Как доказать это строго, я не знаю.


Может быть есть какое-нибудь доказательство попроще?

[mihaild]

Так любое евклидово кольцо факториально, в нём разложение на простые однозначно с точностью ассоциированности. Cоответственно берём каждое простое, на которое делится $P$ или $S$, в максимальной степени, в которой на него всё еще одно из них делится, и все простые перемножаем.

[nnosipov]

Как вариант: доказать, что $[a,b]=ab/(a,b)$. Но для этого нужно предварительно вывести такое свойство: если $AB$ делится на $C$ и при этом $(A,C)=1$, то $B$ делится на $C$.

Формулу $[a,b]=ab/(a,b)$ полезно знать саму по себе, ибо она позволяет быстро найти $[a,b]$ (не прибегая к разложениям $a$ и $b$ на простые элементы).

[EminentVictorians]

mihaild в сообщении #1507904 писал(а):

Cоответственно берём каждое простое, на которое делится $P$ или $S$, в максимальной степени, в которой на него всё еще одно из них делится, и все простые перемножаем.

Я не очень понял это место. Тут вместо $P$ и $S$ имеется в виду $a$ и $b$? Просто $a$ и $b$ могут делится на разные простые, но ассоциированные, и если все эти ассоциированные простые перемножить, то мне кажется получится что-то больше, чем НОК. И даже если все правильно сделать с ассоциированными, как потом доказать, что такое произведение будет делить любое общее кратное $a$ и $b$?

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

Но для этого нужно предварительно вывести такое свойство: если $AB$ делится на $C$ и при этом $(A,C)=1$, то $B$ делится на $C$.

Это я могу. Выразим $(A,C)=1$ линейно через $A$ и $C$: $A\upsilon + C\nu = 1$. Домножим обе части равенства на $B$: $AB\upsilon + CB\nu = B$. В сумме $AB\upsilon + CB\nu$ оба слагаемых делятся на $C$ $\Rightarrow$ $B \vdots C$. Какие дальнейшие действия?

[mihaild]

EminentVictorians в сообщении #1507965 писал(а):

Тут вместо $P$ и $S$ имеется в виду $a$ и $b$?

А этот вопрос я не понял.
Более точно я предлагаю следующий вариант: пусть $f(p, x) = \max \{n : p^n \mid x\}$ - максимальная степень $n$, в которой $p$ делит $x$, эта функция определена для всех простых $p$. Важное свойство: $a \mid b \leftrightarrow \forall p: f(p, a) \leq f(p, b)$.
Тогда $[a, b] = \prod\limits_{p | ab} p^\max\left(f(p, a), f(p, b)\right)$.

EminentVictorians в сообщении #1507965 писал(а):

Просто $a$ и $b$ могут делится на разные простые, но ассоциированные

Это неважно, при поиске НОК ассоциированные элементы можно не различать.