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

Найти наибольший общий делитель (НОД) для двух чисел

Калькулятор "Наибольший общий делитель"

Как найти НОД чисел 12 и 16

Наибольший общий делитель (НОД) двух чисел — наибольшее натуральное число, на которое делятся оба.

12 = 2² × 3

16 = 2⁴

Простое	12	16	Наименьшая степень
2	2²	2⁴	2²
3	3	—	—

— = степень 0: простое не входит в это число, поэтому в НОД его нет.

НОД = 2² = 4

Правило: разложите числа на простые множители; НОД — произведение общих простых множителей, каждый множитель — в наименьшей степени.

Частые пары
Числа	НОД
70 и 385	35
22 и 55	11
12 и 18	6
32 и 176	16
135 и 180	45
24 и 36	12
20 и 30	10
45 и 60	15
16 и 45	1
35 и 39	1

Смотрите также

Наименьшее общее кратное - Найти Наименьшее общее кратное (НОК) для двух чисел
Наибольший общий делитель трёх чисел - Найдите наибольший общий делитель (НОД) трёх чисел
Наименьшее общее кратное трёх чисел - Найдите наименьшее общее кратное (НОК) трёх чисел

FAQ

Что такое наибольший общий делитель двух чисел?

Это наибольшее натуральное число, на которое оба числа делятся без остатка. По-русски его сокращают до НОД, в англоязычных учебниках он же зовётся GCD, GCF или HCF — величина одна и та же. Для 12 и 16 она равна 4.

Как найти НОД разложением на простые множители?

Разложите оба числа на простые множители и перемножьте те, что встречаются в обоих разложениях, столько раз, сколько они входят в каждое из них. 12 = 2 × 2 × 3, 16 = 2 × 2 × 2 × 2, общая часть — 2 × 2, значит НОД равен 4.

Что такое алгоритм Евклида для поиска НОД?

Евклид описал его в «Началах» около 300 года до нашей эры: большее число делят на меньшее, а затем заменяют пару на меньшее число и остаток — и так, пока остаток не станет нулём. Для 16 и 12 это 16 mod 12 = 4, затем 12 mod 4 = 0, то есть НОД равен 4. Раскладывать числа на множители при этом не нужно, поэтому способ работает и там, где разложение уже неподъёмно.