Алгоритм Евклида: найдите НОД(1071, 462) и число квадратов из листа картона

Решение по шагам

1. 1

   Шаг 1. Переводим задачу на язык делимости

   Пусть сторона квадрата равна $a$ мм. Чтобы вдоль длинной стороны уместилось целое число квадратов, нужно, чтобы $1071$ делилось на $a$ без остатка. Аналогично по короткой стороне: $462$ должно делиться на $a$.

   Значит, $a$ — общий делитель чисел 1071 и 462. Квадраты нужны наибольшие, поэтому

   $$a = \text{НОД}(1071,\ 462).$$

   Искать НОД перебором делителей до 462 долго — здесь и нужен алгоритм Евклида.

2. 2

   Шаг 2. Первый шаг алгоритма Евклида

   Алгоритм Евклида в варианте с остатками опирается на свойство

   $$\text{НОД}(a,\ b) = \text{НОД}(b,\ a \bmod b), \qquad b \neq 0.$$

   Большее число заменяется остатком от деления, пара «уменьшается», а НОД при этом не меняется.

   Делим с остатком: $1071 = 2 \cdot 462 + 147$, то есть $1071 \bmod 462 = 147$.

   Следовательно, $\text{НОД}(1071,\ 462) = \text{НОД}(462,\ 147)$. Задача уже стала меньше — повторяем то же действие.