2014 dxdy logo

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

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




 
 Линейное диофантово уравнение
Сообщение23.08.2013, 15:58 
Здравствуйте!
Показать,что число неотрицательных решений диофантова уравнения $ax+by=n$, где $a,b,n\in \mathbb{N}$ и $\text{gcd}(a,b)=1$ равно $\left[\dfrac{n}{ab}\right]$ или $\left[\dfrac{n}{ab}\right]+1$
Моя попытка решения: Это уравнение разрешимо потому что $1=\text{gcd}(a,b)\mid n$.
Пусть $(x_0, y_0)$ некоторое частное решение. Тогда все другие решения имеют вид $(x,y)=(x_0-bt, y_0+at)$ где $t\in \mathbb{Z}$.
Если $-\frac{y_0}{a}\leqslant t \leqslant \frac{x_0}{b},$ тогда все решения будут неотрицательными.
Первый случай: Если $a\mid y_0$ тогда $t$ принимает ровно $\left[\dfrac{x_0}{b}\right]+\dfrac{y_0}{a}+1=\left[\dfrac{n}{ab}-\dfrac{y_0}{a}\right]+\dfrac{y_0}{a}\right+1=\left[\dfrac{n}{ab}\right]+1$ значений.

Второй случай: Но если $a\nmid y_0$ у меня возникают трудности.

Помогите пожалуйста!

 
 
 
 Re: Линейное диофантово уравнение
Сообщение23.08.2013, 19:39 
Похоже, что неявно предполагается, что $a,b\geqslant 0$.
Задача наверняка допускает несколько способов решения.
Можно я намекну на альтернативный вариант?
Как соотносятся между собой множества решений уравнений $ax+by=n$ и $ax+by=n-ab$?

Ward в сообщении #756935 писал(а):
Второй случай: Но если $a\nmid y_0$ у меня возникают трудности.
На $y_0$ в силу произвольности $y_0,t$ можно наложить ограничение $0l\leqslant y_0<a$. Выпишите формулу для числа решений и в этом случае, а потом воспользуйтесь границами на корень для явного вычисления целых частей.

 
 
 
 Re: Линейное диофантово уравнение
Сообщение24.08.2013, 09:26 
Sonic86 в сообщении #757056 писал(а):
На $y_0$ в силу произвольности $y_0,t$ можно наложить ограничение $0l\leqslant y_0<a$. Выпишите формулу для числа решений и в этом случае, а потом воспользуйтесь границами на корень для явного вычисления целых частей.
Уважаемыq Sonic86 возникли у меня такие вопросы:
1) А почему можно наложить такое ограничение на $y_0$?
2) Можете ли Вы объяснить смысл Вашего второго предложения?

 
 
 
 Re: Линейное диофантово уравнение
Сообщение24.08.2013, 09:30 
Ward в сообщении #757183 писал(а):
1) А почему можно наложить такое ограничение на $y_0$?
Потому что $t,y_0$ произвольны. У нас решения имеют вид $...(x_0+2b,y_0-2a),(x_0+b,y_0-a),(x_0,y_0), (x_0-b,y_0+a),(x_0-2b,y_0+2a),...$ и мы можем любое из них принять за $x_0,y_0$. Значит давайте выберем то решение, у которого $0\leqslant y_0<a$ (понятно, что такое решение есть).

Ward в сообщении #757183 писал(а):
2) Можете ли Вы объяснить смысл Вашего второго предложения?
Ммм, какого конкретно?

 
 
 
 Re: Линейное диофантово уравнение
Сообщение24.08.2013, 09:35 
Sonic86 в сообщении #757186 писал(а):
Потому что $t,y_0$ произвольны. У нас решения имеют вид $...(x_0+2b,y_0-2a),(x_0+b,y_0-a),(x_0,y_0), (x_0-b,y_0+a),(x_0-2b,y_0+2a),...$ и мы можем любое из них принять за $x_0,y_0$. Значит давайте выберем то решение, у которого $0\leqslant y_0<a$ (понятно, что такое решение есть).
Спасибо теперь разобрался!
Sonic86 в сообщении #757186 писал(а):
Ммм, какого конкретно?
Выпишите формулу для числа решений и в этом случае, а потом воспользуйтесь границами на корень для явного вычисления целых частей.

 
 
 
 Re: Линейное диофантово уравнение
Сообщение24.08.2013, 10:35 
Ward в сообщении #757189 писал(а):
Выпишите формулу для числа решений и в этом случае, а потом воспользуйтесь границами на корень для явного вычисления целых частей.
Ну я написал, как можно дальше делать. Но я и не заставляю - лучше, если сами будете думать :-)

 
 
 
 Re: Линейное диофантово уравнение
Сообщение24.08.2013, 22:21 
Можно исключить одну переменную, превратив уравнение $ax+by=n$ в делимость $a\mid n-by$. Начнем подставлять $y-0;1;2;...$, тогда $n-by=n;n-b;n-2b;...$ Начиная с какого-то игрека мы найдем решение. Далее, у $y$ "период" решения $a$, коэффициент при $y$ - $b$, значит начиная с первого решения каждое следующее решение лежит на расстоянии $ab$. А сколькими способами можно покрыть без пересечения отрезок $[0;n]$ отрезками длиной $ab$?

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


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