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

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

читает Игорь Тиняков

#элементарнаяматематика #наибольшийобщийделитель #нод #алгоритмевклида

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