НОД нескольких чисел

[mak1610]

Нужно доказать, что
1)НОД (А1,А2...Аn)=НОД (A1,(A2,A3....An))
2)НОД (A1,A2...An)=линейной комбинации

-- Вт сен 06, 2011 00:01:18 --

уточнение к первой НОД (А1,А2...Аn)=НОД (A1,НОД(A2,A3....An))

[SpBTimes]

mak1610 в сообщении #480673 писал(а):

2)НОД (A1,A2...An)=линейной комбинации

какой лин. комбинации?

1) $(a_1, ..., a_{n - 1}) = \delta$
$(\delta, a_n) = d$
Доказать: $(a_1, ..., a_n) = d$
Д-во:
1) Покажем, что d - общий делитель
$(\delta, a_n) = d \Rightarrow \delta \vdots d, a_n \vdots d \Rightarrow a_1 \vdots d ... a_n \vdots d$
2) Покажем, что наибольший
Пусть $d_1$ - общий делитель набора.
$\Rightarrow \delta \vdots d_1, a_n \vdots d_1 \Rightarrow d_1$ общий делитель $\delta$ и $a_n \Rightarrow d \vdots d_1$ чтд

[PAV]

SpBTimes, предупреждение за полное решение простой учебной задачи

[mak1610]

Линейной комбинации Sum UiAi

[ИСН]

Вы что подразумеваете под линейными комбинациями? А то я так тоже скажу, что вообще любое число равно линейной комбинации единицы и нуля, и в каком-то смысле даже буду прав.

[Joker_vD]

Очевидно, что-то вроде $\sum\limits_{i=1}^n \lambda_i A_i$, где $\lambda_i \in \mathbb Z$. Ну, это очень просто, если 1-ое свойство доказано. Глядите, $A_1 = 1\cdot A_1 + 0\cdot A_2$, $A_2 = 0\cdot A_1 + 1\cdot A_2$, теперь поехал алгоритм Евклида: например, $d_1 = A_1 - 5 A_2 = 1\cdot A_1 +(-5)\cdot A_2$, потом $d_2 = A_2 - 6 d_1 = (-6)\cdot A_1 + 30 \cdot A_2$, ну и так далее.