Что такое наибольший общий делитель?

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

Делители числа 12: 1, 2, 3, 4, 6, 12;

Делители числа 36: 1, 2, 3, 4, 6, 9, 12, 18, 36.

Общие делители: 1, 2, 3, 4, 6.

Среди них число 6 наибольшее. Оно и я является наибольшим общим делителем.

Чтобы найти наибольший общий делитель, не всегда удобно перечислять все делители данных чисел, и среди них выбирать потом наибольший общий делитель. Удобнее воспользоваться алгоритмом:

1. Разложить данные числа на простые множители.

2. Выписать те множители, которые входят в разложение обоих чисел.

3. Найти произведение этих множителей. Оно и будет являться наибольшим общим делителем.