Найти НОД(48, 18) используя алгоритм Евклида

Алгоритм Евклида – эффективный способ нахождения наибольшего общего делителя двух чисел, основанный на принципе последовательного вычета остатков от деления.

Принцип работы алгоритма Евклида

Алгоритм Евклида – это метод нахождения наибольшего общего делителя (НОД) двух чисел. Он основан на простом принципе: если два числа a и b имеют общий делитель d, то их разность a – b также имеет общий делитель d.

Принцип работы алгоритма Евклида заключается в последовательном нахождении остатка от деления двух чисел и замене большего числа на этот остаток. Этот процесс повторяется до тех пор, пока остаток не станет равным нулю. Когда это происходит, последнее ненулевое число является наибольшим общим делителем исходных чисел.

Рассмотрим пример:

Пример:

Даны два числа: a = 48 и b = 18.

Сначала мы находим остаток от деления 48 на 18:

48 ÷ 18 = 2 остаток 12

Затем мы заменяем большее число (48) на остаток (12) и повторяем процесс:

18 ÷ 12 = 1 остаток 6

Затем мы снова заменяем большее число (18) на остаток (6) и повторяем процесс:

12 ÷ 6 = 2 остаток 0

Когда остаток становится равным нулю, мы останавливаемся. Последнее ненулевое число (6) является наибольшим общим делителем чисел 48 и 18.

Таким образом, НОД(48, 18) = 6.