Недавно мы говорили про алгоритм Евклида, который используется для поиска наибольшего общего делителя. Сегодня расскажем вам про концепцию, которая появилась как раз благодаря этому алгоритму.
Давайте для начала немного переформулируем сам алгоритм. Для этого заметим такой факт: если мы вычитаем из числа b число a n раз, пока не получится, что 0<b-n*a<a, то фактически мы находим остаток при делении числа b на число a:
b = n*a + r.

Итак, предположим, что мы хотим найти наибольший общий делитель двух чисел a и b, где a<b.

1. Если b делится на a без остатка, то наибольший общий делитель равен a.
2. Если нет, то мы делим b на a с остатком и получаем новую пару чисел (a, r), где r — это остаток от деления b на a.
3. Затем мы повторяем шаги 1 и 2 для пары (a, r).
4. Процесс продолжается до тех пор, пока не получим пару чисел (d, 0), где d — это наибольший общий делитель.

Попробуем применить алгоритм Евклида для чисел a=5 и b=8:
8 = 5*1 + 3
5 = 3*1 + 2
3 = 2*1 + 1
2 = 1*2

А теперь разделим первую строку на a, вторую на r₁ (оно равно 3),третью строку разделим на r₂=2, а четвертую — на r₃=1. Получим:
8/5 = 1 + 3/5
5/3 = 1+2/3
3/2 = 1+1/2
2=2