Билет 2. 3. НОД: алгоритм нахождения.

Алгоритм разложения на простые множители:

1. Разложить каждое число на простые множители.
2. Выбрать только общие простые множители и для каждого взять наименьшую степень.
3. Перемножить выбранные множители.

Например, \(12=2^2\cdot3\), \(18=2\cdot3^2\). Общие множители с наименьшими степенями: \(2\) и \(3\). Следовательно, \(\text{НОД}(12,18)=2\cdot3=6\).