По разложению. НОД — произведение общих простых множителей, каждый в наименьшей степени; НОК — произведение всех простых множителей, каждый в наибольшей степени: 120 = 2³ · 3 · 5, 126 = 2 · 3² · 7, НОД = 2 · 3 = 6, НОК = 2³ · 3² · 5 · 7 = 2520. Всегда НОК(a, b) · НОД(a, b) = a · b.
Алгоритм Евклида не требует разложения: делим большее число на меньшее с остатком, затем меньшее — на остаток, и так далее; последний ненулевой остаток — НОД.
203 = 91 · 2 + 21, 91 = 21 · 4 + 7, 21 = 7 · 3 — НОД(203, 91) = 7.
Если НОД равен 1, числа взаимно простые.
Квадраты из прямоугольника. От прямоугольника a × b (a > b) отрезают квадраты со стороной b, сколько поместится, — это неполное частное a : b; из остатка b × r — квадраты со стороной r, и т. д. Всего квадратов — сумма неполных частных алгоритма Евклида, а сторона самого маленького — НОД(a, b).