Алгоритм Евклида, доказательство

[ИС]

Что-то я никак не пойму.
Вот есть у нас 2 натуральных числа $ a>1, b>1$ и пусть, например $a > b $
Тогда

$a = b\cdot q_1 + r_1$
$b = r_1\cdot q_2 + r_2$
$r_1 = r_2\cdot q_3 + r_3$

......................................

$r_{k-1} = r_{k}\cdot q_{k+1} + r_{r+1}$
$r_{k} = r_{k+1}\cdot q_{k+2} + 0 $

Вот понимаю что $r_{k+1}$ будет общим делителем для $r_{k}, r_{k-1} ..... r_{1}, a , b$
Но почему он будет именно наибольшим делителем для этих чисел никак не пойму....
Объясните пожалуйста.

[nnosipov]

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

Но почему он будет именно наибольшим делителем для этих чисел никак не пойму....

Потому что он делится на любой другой общий делитель (а почему делится, поймите сами).

[gris]

А вы покажите, что любой общий делитель $a$ и $b$ делит и $r_{k+1}$.
При переходе к каждой следующей паре именно наибольший общий делитель остаётся инвариантом.
То есть $GCD(r_i,r_{i+1})=GCD(r_{i+1},r_{i+2})$.

[ИС]

Есть! я, кажется понял!

Посмотрите пожалуйста, правильно ли я доказываю?

Вот есть у нас 2 натуральных числа $ a>1, b>1$ и пусть, например $a > b $
буду делить a на b с остатком

$a = b\cdot q_1 + r_1$

затем разделю делитель b на остаток

$b = r_1\cdot q_2 + r_2$

и тут разделю делитель ($r_1$) на остаток ($r_2$) и так до тех пор пока остаток не окажется равным нулю.

$a = b\cdot q_1 + r_1$ (1)
$b = r_1\cdot q_2 + r_2$ (2)
$r_1 = r_2\cdot q_3 + r_3$ (3)

......................................

$r_{k-1} = r_{k}\cdot q_{k+1} + r_{r+1}$ (4)
$r_{k} = r_{k+1}\cdot q_{k+2} + 0 $ (5)

"двигаясь по этому столбцу формул вверх", я получу, что $r_{k+1}$ - общий делитель чисел a и b. А "двигаясь сверху вниз", я буду рассуждать так.

< Начало рассуждения_1>
пусть l = НОД(a,b);
$ a = l \cdot d_{a} $ // а можно представить в виде произведения НОДа и натурального числа.
$b =l \cdot d_{b}$ // аналогично

тогда из (1) получаю что

$l \cdot d_{a}= l\cdot d_{b}\cdot q_1 + r_1$

$ r_1 = l\cdot(d_{a} - d_{b}\cdot q_1) $

$ r_1 $ делится на НОД(a,b)
< конец рассуждения_1>

Рассуждая аналогично рассуждению_1, я замечу что и $ r_2 $ делится на НОД(a,b), $ r_3$ делится на НОД(a,b) ....$ r_{k+1}$ делится на НОД(a,b).

А так как НОД(a,b) он НОД(a,b), то из всех общих делителей чисел а и b , на НОД(a,b) может делиться только НОД(a,b), значит $ r_{k+1} =$ НОД(a,b).


ЗЫ Это, последние, предложение можно как-нить вообще по человечески записать?

[nnosipov]

В принципе, и так нормально. Главное, что Вы осознали необходимость обоих движений: как снизу вверх, так и сверху вниз.

[ИС]

оказывается это можно было доказать проще.

Можно прям сходу доказать, что для НОД(а,b) = НОД(b,r), где r - остаток от деления числа a на b.

пусть$ l$ - общий делитель $a$ и $b$, тогда он очевидно будет и общем делителем чисел $r$ и $b$
аналогично, если $l_{1}$ - общий делитель чисел $r$ и $b$ то он будет и общим делителем чисел $a$ и $b$.
Т.е. вообще все общие делители чисел $a$ и $b$ и общие делители чисел $r$ и $b$ совпадают, а это и означает что НОД(а,b) = НОД(b,r)