Книга: Путеводитель для влюбленных в математику
Назад: 135
Дальше: 141

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. Так как алгоритм Евклида позволяет эффективно вычислить НОД двух чисел, он также позволяет выяснить, являются ли два числа взаимно простыми.
Назад: 135
Дальше: 141