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