Достаточно просто. Надо лишь перемножить множители, которые встречаются в обоих разложениях.
Пример:
а = 2³ × 3 × 5³ × 7²
b = 2² × 5³ × 7
В обоих разложениях присутствуют 2², 5³ и 7. Перемножим:
НОД(а, b) = 2² × 5³ × 7
(с вашего позволения считать не буду. Тут важен был принцип. Он, надеюсь, понятен)