Калькулятор НОД и НОК
Найдите наибольший общий делитель (НОД) и наименьшее общее кратное (НОК) двух натуральных чисел. Калькулятор показывает решение по алгоритму Евклида.
Примеры
НОД = 6, НОК = 144
НОД (наибольший общий делитель)
6
НОК (наименьшее общее кратное)
144
Ход алгоритма Евклида
48 = 2 \times 18 + 12, 18 = 1 \times 12 + 6, 12 = 2 \times 6 + 0
Связь: A x B = НОД x НОК
48 \times 18 = 864 = 6 \times 144
НОД равен 6, НОК равен 144.
Это было полезно?
Примеры
Как это работает
Формула
Переменные
- Первое натуральное число
- Второе натуральное число
Сначала калькулятор находит НОД по алгоритму Евклида: последовательно делит большее число на меньшее и переносит остаток в следующий шаг, пока остаток не станет равен 0. Последний ненулевой остаток — это НОД. После этого НОК вычисляется из тождества для произведения двух чисел.
Примените рекуррентный шаг Евклида: заменяйте на , пока . Оставшееся значение будет НОД. НОК затем получается из равенства .
Частые вопросы
01Что такое НОД?
НОД, или наибольший общий делитель, — это самое большое натуральное число, на которое оба исходных числа делятся без остатка.
02Что такое НОК?
НОК, или наименьшее общее кратное, — это самое маленькое натуральное число, которое делится на оба исходных числа.
03Как работает алгоритм Евклида?
Большее число делят на меньшее, затем меньшее — на полученный остаток. Так продолжают, пока остаток не станет равен нулю; последний ненулевой остаток и есть НОД.
04Как связаны НОД и НОК?
Для любых натуральных чисел a и b верно: a x b = НОД(a,b) x НОК(a,b). Поэтому НОК можно найти как (a x b) / НОД(a,b).
05Что значит «взаимно простые числа»?
Два числа называют взаимно простыми, если их НОД равен 1. Это означает, что у них нет общих делителей, кроме 1.