2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Доказать утверждение
Сообщение06.11.2012, 23:10 
Аватара пользователя
Для любых чисел $a, b, c $ уравнение $ax+by=c$ имеет решение тогда и только тогда когда $c$ делится на $(a, b)$. Написано, что
Цитата:
Доказательство следует из очевидного факта, что линейная комбинация двух чисел по-прежнему должна делиться на их общий делитель.
Но для меня это не очевидно.

 
 
 
 Re: Доказать утверждение
Сообщение06.11.2012, 23:18 
Аватара пользователя
Вынесите общий делитель за скобки.

 
 
 
 Re: Доказать утверждение
Сообщение06.11.2012, 23:23 
Аватара пользователя
$d\left(\frac{a}{d}x+\frac{b}{d}y\right)=ax+by, \frac{a}{d}x+\frac{b}{d}y\in\mathbb{Z}$

 
 
 
 Re: Доказать утверждение
Сообщение07.11.2012, 12:19 
fiztech в сообщении #640962 писал(а):
Но для меня это не очевидно.
Для меня тоже. Ведь приведённая цитата объясняет, почему верно утверждение "только тогда". А для доказательства утверждения "тогда" необходимы дополнительные аргументы (алгоритм Евклида, например).

 
 
 
 Re: Доказать утверждение
Сообщение07.11.2012, 16:08 
Аватара пользователя
Необходимость очевидна.
Достаточность: Дано, что $(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$.

 
 
 
 Re: Доказать утверждение
Сообщение07.11.2012, 16:31 
Аватара пользователя
xmaister
$d$ это наибольший общий делитель $(a,b)$?

 
 
 [ Сообщений: 6 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group