Основная теорема о наибольшем общем делителе | Решение уравнений в целых числах

Продолжаем курс, начатый в лекции про наибольший общий делитель и наименьшее общее кратное (лекцию можно найти по ссылке ) и сегодня докажем основную теорему о наибольшем общем делителе. Вспомним алгоритм Евклида, которым мы пользовались для нахождения наибольшего общего делителя двух чисел. А после мы представим НОД(a,b)=ax by, и вы увидите, как это можно сделать с помощью алгоритма Евклида, поднимаясь по нему снизу вверх, а также познакомитесь и с другим, очень простым приемом. Параллельно мы поговорим о решении линейных уравнений в целых числах (диофантовых уравнениях, как их еще называют) с несколькими переменными, и докажем теорему, которая представляет собой необходимое и достаточное условие разрешимости таких уравнений. Из этой теоремы мы легко получим и основную теорему о наибольшем общем делителе. Мы с вами уже решали линейные уравнения с двумя неизвестными в целых числах. В конце лекции разберем еще одно уравнение, но уже с тремя неизвестными, на котором рассмотрим другой прием решения подобных уравнений. читает Игорь Тиняков #элементарнаяматематика #наибольшийобщийделитель #нод #алгоритмевклида