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