Расширенный алгоритм евклида для "школьника".

[boriska]

Где про него максимально просто написано с примерами? Гугл выдает либо "запроганный" алгоритм, либо с символами непривычными без расшифровки.

Вот:
1) http://algolist.manual.ru/maths/teornum/nod.php (с программным кодом)
2) http://e-maxx.ru/algo/export_extended_euclid_algorithm (с какими-то скобками странными и %)
И так везде, очень странно....

[svv]

По первой ссылке: там, где написано «Псевдокод» — это всё-таки для Вас, а не для компьютера.
По второй: там всё объяснено. a%b — так в некоторых языках программирования обозначается остаток от деления a на b.

[boriska]

svv в сообщении #992264 писал(а):

По первой ссылке: там, где написано «Псевдокод» — это всё-таки для Вас, а не для компьютера.

Но все равно, в коде этом копаться очень неудобно...

[svv]

Попробуйте представить этот алгоритм в форме заполнения таблицы с четырьмя столбцами. В таком виде пункт 3.2 не нужен.

[boriska]

svv в сообщении #992274 писал(а):

Попробуйте представить этот алгоритм в форме заполнения таблицы с четырьмя столбцами. В таком виде пункт 3.2 не нужен.

Как представить, откуда взять таблицу и понять связь в ней?

[svv]

Пусть $a=37, b=11$. Сначала пишем
$\begin{matrix}&37&1&0\\{.}&11&0&1\end{matrix}$

Числа, только что дописанные, помечаю синим.

Затем:
$\begin{matrix}&37&1&0\\\color{blue}3&11&0&1\\&\color{blue}4&\color{blue}1&\color{blue}-3\end{matrix}$

Здесь $\color{blue}3$ — это частное $37:11$. Потом, используя это частное, получаем числа нижней строки:
$37-{\color{blue}3}\cdot 11={\color{blue}4} \quad\quad 1-{\color{blue}3}\cdot 0={\color{blue}1} \quad\quad 0-{\color{blue}3}\cdot 1={\color{blue}-3}$.

Затем аналогично:
$\begin{matrix}&37&1&0\\3&11&0&1\\\color{blue}2&4&1&-3\\&\color{blue}3&\color{blue}-2&\color{blue}7\end{matrix}$

Затем:
$\begin{matrix}&37&1&0\\3&11&0&1\\2&4&1&-3\\\color{blue}1&3&-2&7\\&\color{blue}1&\color{blue}3&\color{blue}-10\end{matrix}$

Затем:
$\begin{matrix}&37&1&0\\3&11&0&1\\2&4&1&-3\\1&3&-2&7\\\color{blue}3&1&3&-10\\&\color{blue}0&&\end{matrix}$
Стоп.

Попробуйте понять, как заполняется таблица на каждом шаге.

[demolishka]

Для простоты рассмотрим случай взаимно простых $a$ и $b$. Тогда вам надо найти такие $x$ и $y$, что $ax + by = 1$.
Запустим алгоритм Евклида например для $a=17$ и $b=13$:

$$17 = 1 \cdot 13 + 4,$$

$$13 = 3 \cdot 4 + 1,$$

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

$$1=13 - 3 \cdot 4.$$

Из первого равенства можно выразить четверку и подставить в предыдущее равенство.

$$1 = 13 - 3 \cdot (17 - 1 \cdot 13).$$

Раскроем скобки и получим искомое разложение единички

$$1 = 4\cdot 13 - 3\cdot 17.$$

Понятно, что в общем случае, поднимаясь вот так вот снизу вверх через выражение остатков на каждом шаге, мы в конце концов к придем к нужному выражению НОД. Проделайте тоже самое, например, для $a=325$ и $b=117$.