Что такое НОД?

НОД двух чисел – это самое большое число, которое одновременно является делителем каждого из них. Например, для чисел 12 и 18:

• Делители 12: 1, 2, 3, 4, 6, 12.
• Делители 18: 1, 2, 3, 6, 9, 18.

Наибольший общий делитель: 6.

Как найти НОД?

Наиболее распространённый метод нахождения НОД – это алгоритм Евклида. Вот его шаги:

1. Если числа $a$ и $b$, причём $a>b$, то найдите остаток от деления $a$ на $b$: $r=a\mathrm{m}\mathrm{o}\mathrm{d}b$.
2. Замените $a$ на $b$ и $b$ на $r$.
3. Повторяйте, пока $b$ не станет равным нулю. В этот момент $a$ будет равен НОД.

Формула алгоритма Евклида:

Пример нахождения НОД для чисел 48 и 18:

1. $48\mathrm{m}\mathrm{o}\mathrm{d}18=12$.
2. $18\mathrm{m}\mathrm{o}\mathrm{d}12=6$.
3. $12\mathrm{m}\mathrm{o}\mathrm{d}6=0$.

Ответ: 6.