Например, если a = 100 и b = 40, частное q = 2 и остаток c = 20. Иными словами, 100 – 2 × 40 = 20.
136
10 693 = 4 × 2220 + 1813.
137
2220 = 1 × 1813 + 407.
138
1813 = 4 × 407 + 185.
139
407 = 2 × 185 + 37.
140
В главе 6 мы познакомились с концепцией взаимно простых чисел. Вот альтернативное определение: число a взаимно простое с b, если НОД (a, b) = 1. Так как алгоритм Евклида позволяет эффективно вычислить НОД двух чисел, он также позволяет выяснить, являются ли два числа взаимно простыми.
