344
правки
Изменения
→Стандартный алгоритм Евклида
: <tex> a,\, b,\,r_1 > r_2 > r_3 > r_4 > \cdots >r_n</tex>
определена тем, что каждое <tex>r_k</tex> — это остаток от деления предпредыдущего числа на предыдущее, а предпоследнее делится на последнее нацело, то есть
: <tex>a = bq_0 b \cdot q_0 + r_1</tex>: <tex>b = r_1q_1 r_1 \cdot q_1 + r_2</tex>: <tex>r_1 = r_2q_2 r_2 \cdot q_2 + r_3</tex>
: <tex>\cdots</tex>
: <tex>r_{k-2} = r_{k-1} \cdot q_{k-1} + r_k</tex>
: <tex>\cdots</tex>
: <tex>r_{n-1} = r_n \cdot q_n</tex>
Тогда <tex>\gcd(a, b) = r_n</tex> {{---}} последний ненулевой член этой последовательности.
