С помощью алгоритма Евклида найти НОД 1317; 2553

Алгоритм Евклида — это эффективный метод для нахождения наибольшего общего делителя (НОД) двух чисел. Давайте найдем НОД для чисел 1317 и 2553, используя этот алгоритм.

1. Начнем с деления большего числа (2553) на меньшее (1317) и найдем остаток: \[ 2553 \div 1317 = 1 \quad \text{(целая часть)} \] \[ 2553 - 1317 \times 1 = 1236 \quad \text{(остаток)} \]

2. Теперь применяем алгоритм снова, заменяя 2553 на 1317 и 1317 на остаток 1236: \[ 1317 \div 1236 = 1 \] \[ 1317 - 1236 \times 1 = 81 \]

3. Продолжаем процесс: \[ 1236 \div 81 = 15 \] \[ 1236 - 81 \times 15 = 21 \]

4. Снова делим: \[ 81 \div 21 = 3 \] \[ 81 - 21 \times 3 = 18 \]

5. Продолжаем: \[ 21 \div 18 = 1 \] \[ 21 - 18 \times 1 = 3 \]

6. Последние шаги: \[ 18 \div 3 = 6 \] \[ 18 - 3 \times 6 = 0 \]

Когда мы получили остаток 0, последний ненулевой остаток — это и есть НОД.

Таким образом, НОД 1317 и 2553 равен 3.