Что называется наибольшим общим делителем двух натуральных чисел?
Ответов: 2
У любого натурального числа есть делители - числа, на которые это число делится без остатка. даже у простых чисел такие делители есть - само это число и единица. Если взять два натуральных числа, то у них также есть свои делители, которые иногда могут совпадать с делителями второго числа. А делитель единица присутствует всегда, но рассматривать его не интересно. Так вот, самый большой по значению делитель, который является общим для обеих чисел будет этим пресловутым наибольшим делителем. Находят его по алгоритму Евклида, который очень прост и состоит в следующем. Из имеющейся пары чисел составляется новая пара, в котором одно число - меньшее из первоначальных, а второе разница между ними. потом операция повторяется пока ода полученных числа не совпадут. Это и есть наибольший делитель. По приведенному примеру для чисел 8 и 12 получаем вторую пару чисел 8 и 4 (12-8), следующая пара будет 4 и 4 (8-4). Числа совпали уже во второй итерации и мы нашли наибольший делитель - это 4.
По порядку.
Натуральное число - число, возникшее в результате подсчета реальных вещей (яблок, баранов, телевизоров), которое используют для определения их количества.
Два натуральных числа - это понятно. Мы имеем два числа, не совпадающих друг с другом.
Общий делитель двух натуральных чисел - число, на которое может быть разделено каждое из двух натуральных чисел без остатка. Любые два натуральных числа имеют как минимум один общий делитель - единицу.
Если два натуральных числа имеют несколько общих делителей, то можно определить наибольший из них. К примеру, 12 и 8 имеют общие делители: 1, 2, 4. Соответственно, 4 будет наибольшим общим делителем для 12 и 8.
Чтобы найти НОД, нужно разложить каждое из чисел на простые множители. Если речь идет о больших числах, НОД которых трудно определить, применяют алгоритм Евклида или бинарный алгоритм.
Похожие вопросы
Добавить комментарий