Калькулятор Tiger Algebra

Наибольший общий делитель (НОД) — это наибольшее положительное целое число, на которое можно разделить множество целых чисел. Например, наибольшее число, на которое можно разделить 12, 24 и 32, равно 4, а значит, наибольший общий делитель равен 4. Еще один пример: наибольшее число, на которое можно разделить 3, 5 и 10, равно 1, поэтому их наибольший общий делитель равен 1.

Существует два способа найти наибольший общий делитель: перечисление множителей (=делителей) каждого числа и разложение на простые множители.

Способ 1: перечисление множителей (=делителей) каждого числа
Необходимо перечислить все множители каждого числа и определить наибольший множитель (=делитель), общий для всех чисел.

12 - 1, 2, 3, 4, 6, 12
24 - 1, 2, 3, 4, 6, 8, 12, 24
32 - 1, 2, 3, 4, 8, 16, 32

4 является наибольшим делителем, общим для приведенных чисел, а значит, это наибольший общий делитель.

Способ 2: разложение на простые множители
Необходимо использовать древовидное представление множителей, чтобы определить простые множители (являющиеся простыми числами) каждого числа. Затем следует определить простые множители, общие для всех чисел, и перемножить их, чтобы получить наибольший общий делитель.

Простыми множителями всех чисел являются 2 и 2. После перемножения получается наибольший общий делитель — 4.