НОД, НОК и алгоритм Евклида
Наибольший общий делитель и наименьшее общее кратное — через разложение на множители и через алгоритм Евклида, а на последнем уровне — уравнения Безу ax + by = c в целых числах.
Как решать
НОД — самое большое число, на которое делятся оба числа; НОК — самое маленькое, которое делится на оба. Для небольших чисел их видно из разложения на простые множители, а для больших быстрее алгоритм Евклида: он делит с остатком, не раскладывая ничего.
По шагам
- Через разложение: НОД — общие простые множители в наименьших степенях, НОК — все множители в наибольших степенях.
- Алгоритм Евклида: разделите большее число на меньшее с остатком, затем делитель — на остаток, и так далее, пока остаток не станет нулём. Последний ненулевой остаток — НОД.
- НОК найдите через НОД: $\text{НОК}(a, b) = \frac{a \cdot b}{\text{НОД}(a, b)}$.
- Уравнение $ax + by = c$ решается, только если $c$ делится на $\text{НОД}(a, b)$. Пройдите алгоритм Евклида обратно, выразив НОД через $a$ и $b$, и умножьте на $\frac{c}{\text{НОД}}$.
Где ошибаются
- В НОД берут множители в наибольшей степени, а в НОК — в наименьшей. Наоборот: НОД не может быть больше меньшего из чисел.
- В алгоритме Евклида берут в ответ нулевой остаток или последнее частное. Ответ — последний ненулевой остаток.
- В уравнении Безу забывают проверить делимость: у $6x + 9y = 7$ целых решений нет, потому что $7$ не делится на $3$.
- Думают, что решение уравнения Безу одно. Их бесконечно много: к $x$ можно прибавлять $\frac{b}{d}t$, вычитая из $y$ величину $\frac{a}{d}t$.