Линейное диофантово уравнение

[Ward]

Здравствуйте!
Показать,что число неотрицательных решений диофантова уравнения $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$ у меня возникают трудности.

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

[Sonic86]

Похоже, что неявно предполагается, что $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$. Выпишите формулу для числа решений и в этом случае, а потом воспользуйтесь границами на корень для явного вычисления целых частей.

[Ward]

Sonic86 в сообщении #757056 писал(а):

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

Уважаемыq Sonic86 возникли у меня такие вопросы:
1) А почему можно наложить такое ограничение на $y_0$?
2) Можете ли Вы объяснить смысл Вашего второго предложения?

[Sonic86]

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) Можете ли Вы объяснить смысл Вашего второго предложения?

Ммм, какого конкретно?

[Ward]

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 писал(а):

Ммм, какого конкретно?

Выпишите формулу для числа решений и в этом случае, а потом воспользуйтесь границами на корень для явного вычисления целых частей.

[Sonic86]

Ward в сообщении #757189 писал(а):

Выпишите формулу для числа решений и в этом случае, а потом воспользуйтесь границами на корень для явного вычисления целых частей.

Ну я написал, как можно дальше делать. Но я и не заставляю - лучше, если сами будете думать

[Sonic86]

Можно исключить одну переменную, превратив уравнение $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$?