Чтобы найти наибольший общий делитель двух чисел, нужно разложить эти числа на простые множители и найти произведение их совместных простых множителей, взятых с наименьшим показателем степени.
Например, найдём НОД (48 и 36)
48 = 2 * 2 * 2 * 2 * 3
36 = 2 * 2 * 3 * 3
НОД (48; 36) = 2 * 2 * 3 = 12 - наибольший общий делитель
48 : 12 = 4 36 : 12 = 3