Для любых натуральных чисел \(a\) и \(b\), \( a > b \), имеет место соотношение \( \text{НОД} (a, b) = \text{НОД} (r, b) = \ldots = \text{НОД} (r_n, r_{n - 1}) = r_n \), где \(r_n\) \(-\) последний отличный от нуля остаток в системе:

Доказательство

\[
a = bq_1 + r_1, \text{ где } 0< r_1 < b,
\] \[
b = r_1 q_2 + r_2, \text{ где } 0< r_2 < r_1,
\] \[
r_1 = r_2 q_3 + r_3, \text{ где } 0< r_3 < r_2,
\] \[
\ldots \ldots \ldots \ldots \ldots \ldots
\] \[
r_{n - 2} = r_{n - 1} q_n + r_n, \text{ где } 0< r_n < r_{n - 1},
\] \[
r_{n - 1} = r_{n} q_{n + 1} + r_{n + 1}, \text{ где } r_{n + 1} = 0,
\]

Очевидно, что \(a > b > r_1 > r_2 > ... > r_{n-1}\). Если все числа в нашей цепочке положительные, то в конечном итоге мы получим ноль. На этом строится все рассуждение.