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

135

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