Доказать утверждение

[fiztech]

Для любых чисел $a, b, c $ уравнение $ax+by=c$ имеет решение тогда и только тогда когда $c$ делится на $(a, b)$. Написано, что

Цитата:

Доказательство следует из очевидного факта, что линейная комбинация двух чисел по-прежнему должна делиться на их общий делитель.

Но для меня это не очевидно.

[olenellus]

Вынесите общий делитель за скобки.

[xmaister]

$d\left(\frac{a}{d}x+\frac{b}{d}y\right)=ax+by, \frac{a}{d}x+\frac{b}{d}y\in\mathbb{Z}$

[nnosipov]

fiztech в сообщении #640962 писал(а):

Но для меня это не очевидно.

Для меня тоже. Ведь приведённая цитата объясняет, почему верно утверждение "только тогда". А для доказательства утверждения "тогда" необходимы дополнительные аргументы (алгоритм Евклида, например).

[Whitaker]

Необходимость очевидна.
Достаточность: Дано, что $(a,b)\mid n$.
Рассмотрим множество $S=\{ax+by \mid x, y\in \mathbb{Z}\}$
Это множество является модулем, т.е. $\forall m, n\in S$ должно быть $m-n\in S$. Если модуль нетривиальный (т.е. не пустой), то легко доказать, что все числа модуля явлются целыми кратными некоторого положительного числа.
Пусть $ax_0+by_0$ - наименьшее положительное число вида $ax+by$.
Основываясь на том, что я сказал нетрудно показать, что $(a,b)=ax_0+by_0$.
Но так как по условию $(a,b)\mid n$, то $ax_0+by_0\mid n$.
Значит, $\exists t\in \mathbb{Z}$ такое, что $t(ax_0+by_0)=n$ или $a(tx_0)+b(ty_0)=n$, т.е. $(tx_0, ty_0)$ - решение уравнение $ax+by=n$.

[fiztech]

xmaister
$d$ это наибольший общий делитель $(a,b)$?