Наибольший общий делитель (НОД) — это наибольшее число, которое делит два или более целых числа без остатка. Для чисел 12 и 18 делителями являются 1, 2, 3, 6, поэтому НОД равен 6. НОД также называют наибольшим общим делителем.

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

Наибольший общий делитель (НОД) упрощает дроби. Деление числителя и знаменателя на их НОД сводит дробь к наименьшим членам. Он также встречается в модульной арифметике, криптографии и теории чисел. Наименьшее общее кратное связано с НОД формулой НОК(a, b) = a × b / НОД(a, b).

• Наибольшее число, делящее целые числа нацело.
• Найден с помощью алгоритма Евклида.
• Используется для упрощения дробей.
• Связывается с НОК простой формулой