НОД(a, b) — наибольший общий делитель, НОК(a, b) — наименьшее общее кратное. Они связаны формулой НОД · НОК = a · b. Алгоритм Евклида находит НОД без разложения на множители: делим большее на меньшее с остатком, пока остаток не станет нулём — последний ненулевой остаток и есть НОД.
Повторить теорию