Теорема о линейном представлении НОД.

[Toms]

Не имея под рукой надлежащих учебных пособий и не имея возможности ими обзавестись, я натолкнулся на вопрос.
Если c=НОД(a,b), (a>b) то можно представить наибольший общий делитель чисел а и b в виде:
a*x+b*y=c,
где х и у - целые. Но как это доказать
Была идея представить число a как bq+r, но куда девать переменные?
Теорию чисел вынужден самостоятельно учить второй день.
google.com не помог.

[Профессор Снэйп]

Индукция по $a + b$

Если $a + b = 1$, то берём $x = 1$, $y = 0$ и представление готово. Далее, так как $\text{НОД}(a,b) = \text{НОД}(a-b,b)$, то $c = (a-b)x' + by' = ax' + b(y'-x')$ и берём $x = x'$, $y = y'-x'$.

А можно и без всякой индукции. Имеем $I = \{ ax + by : x,y \in \mathbb{Z} \}$ --- идеал в $\mathbb{Z}$. Выбираем в этом идеале положительный элемент с минимальным модулем. Это как раз и будет $c$

[Leox]

Точнее - в $\mathbb{Z}$ все идеалы главные поетому $I =c \mathbb{Z} $ для некоторого $c.$

[mihailm]

Toms в сообщении #427911 писал(а):

Не имея под рукой надлежащих учебных пособий и не имея возможности ими обзавестись, я натолкнулся на вопрос.
...

Куроша посмотрите Курс высшей алгебры
представление получается из алгоритма Евклида получения НОДа

[VAL]

Toms в сообщении #427911 писал(а):

Но как это доказать?
...
google.com не помог.

Предложено уже много вариантов...
Но меня удивила последняя фраза.
Как Вы гуглили, чтобы ухитриться не найти нужного?!
Набрал в поисковике "НОД". Первой же ссылкой открылась статья в википедии, в которой есть и нужное Вам утверждение, и указание на метод доказательства. и ссылка на это доказательство.

[Toms]

mihailm в сообщении #427939 писал(а):

Toms в сообщении #427911 писал(а):

Не имея под рукой надлежащих учебных пособий и не имея возможности ими обзавестись, я натолкнулся на вопрос.
...

Куроша посмотрите Курс высшей алгебры

Нету. В "Основах Теории Чисел" И.М. Виноградова тоже нет, а это пока все, что я смог найти у себя на полках.

Профессор Снэйп, спасибо большое.