153
правки
Изменения
→Стандартный алгоритм Евклида
===Стандартный алгоритм Евклида===
Пусть <math>a</math> и <math>b</math> — целые числа, не равные одновременно нулю, и последовательность чисел
: <math> a,\, b,\,r_1 > r_2 > r_3 > r_4 > \cdots >r_n</math>
определена тем, что каждое <math>r_k</math> — это остаток от деления предпредыдущего числа на предыдущее, а предпоследнее делится на последнее нацело, то есть
: <math>a = bq_0 + r_1</math>
: <math>b = r_1q_1 + r_2</math>
: <math>r_1 = r_2q_2 + r_3</math>
: <math>\cdots</math>
: <math>r_{k-2} = r_{k-1} q_{k-1} + r_k</math>
: <math>\cdots</math>
: <math>r_{n-1} = r_n q_n</math>
Тогда НОД(''a'',''b''), наибольший общий делитель <math>a</math> и <math>b</math>, равен
<math>r_n</math>, последнему ненулевому члену этой последовательности.
'''Существование''' таких <math>r_1, r_2, ...</math>, то есть возможность деления с остатком <math>m</math> на <math>n</math> для любого целого <math>m</math> и целого <math>n\ne 0</math>, доказывается [[Математическая индукция|индукцией]] по ''m''.
'''Корректность''' этого алгоритма вытекает из следующих двух утверждений:
* Пусть <math>a = bq + r</math>, тогда <math>\gcd (a,b) = \gcd (b,r).</math>
{{Hider|
title = '''Доказательство'''|
hidden = 0 |
title-style = text-align: left; height: auto; |
content-style = text-align: left; |
content =
# Пусть k — любой общий делитель чисел a и b, не обязательно максимальный, тогда <math> a = t_1 * k </math> ; <math> b = t_2 * k; </math> где <math> t_1 </math> и <math> t_2 </math> — целые числа из определения.
# Тогда k также общий делитель чисел b и r, так как b делится на k по определению, а <math>r = a - bq = (t_1 - t_2*q)*k </math> (выражение в скобках есть целое число, следовательно, k делит r без остатка)
# Обратное также верно и доказывается аналогично 2) - любой делитель b и r так же является делителем a и b.
# Следовательно, все общие делители пар чисел a,b и b,r совпадают. Другими словами, нет общего делителя у чисел a,b, который не был бы также делителем b,r, и наоборот.
# В частности, максимальный делитель остается тем же самым. Что и требовалось доказать.
}}
* <math>\gcd (0,r) = r</math> для любого ненулевого <math>r.</math>
Проще сформулировать алгоритм Евклида так: если даны натуральные числа <math>a</math> и <math>b</math> и, пока получается положительное число, по очереди вычитать из большего меньшее, то в результате получится НОД.
===Расширенный алгоритм Евклида===
