Условие
Найдите НОД чисел 240 и 46 и целые u,v, для которых 240u+46v=НОД(240,46).
Решение по шагам
Последовательность делений: 240=5·46+10; 46=4·10+6; 10=6+4; 6=4+2; 4=2·2. Последний ненулевой остаток равен 2.
Разворачиваем: 2=6−4=2·6−10=2(46−4·10)−10=2·46−9·10=2·46−9(240−5·46)=−9·240+47·46. Значит подходят u=−9, v=47.
Проверка результата
Подстановка даёт −2160+2162=2. Число 2 делит оба исходных числа; обратные преобразования доказывают, что любой их общий делитель делит 2.
Типичная ошибка
Остановиться на остатке 4 нельзя: ещё одно деление даёт 2. Коэффициенты нужно восстанавливать с исходными числами, а не с промежуточными остатками.
Что даёт этот метод
Тождество Безу помогает решать линейные диофантовы уравнения и находить обратные элементы по модулю. Коэффициенты не единственны.
Дальше по теме
Комбинаторика и дискретная математика: другие задачи и разборы.
Учебное условие и объяснение сформулированы редакцией damirock.com. Это самостоятельный разбор, а не официальный билет или ключ экзамена. Числа относятся к модели задачи.