42
правки
Изменения
→Стандартный алгоритм Евклида
===Стандартный алгоритм Евклида===
{{Теорема|statement=
Пусть <tex>a</tex> и <tex>b</tex> — целые числа, не равные одновременно нулю, и последовательность чисел
: <tex> a,\, b,\,r_1 > r_2 > r_3 > r_4 > \cdots >r_n</tex>
: <tex>r_{n-1} = r_n q_n</tex>
Тогда НОД<tex>\gcd(''a'',''b''), наибольший общий делитель <tex>a</tex> и <tex>b</tex>, равен<tex>= r_n</tex>, {{---}} последнему ненулевому члену этой последовательности.}}
'''Существование''' таких <tex>r_1, r_2, ...</tex>, то есть возможность деления с остатком <tex>m</tex> на <tex>n</tex> для любого целого <tex>m</tex> и целого <tex>n\ne 0</tex>, доказывается индукцией по ''m''.
