How can I show that there is a unique integer solution $(x_1, y_1)$ to the Diophantine equation $ax+by=c$ such that $0\leq x_1< b/\gcd(a,b)$?
I am given $a,b,c\in\mathbb{Z}^{+}$ such that $\gcd(a,b)|c$. I gave it a try first. I made $\gcd(a,b)=d$ and $d$ is a positive integer for sure. Then, we know $d|a$, $d|b$, and $d|c$. By divisibility rules, $d|(ax+by)$, so $d|c$. I've come full circle.
The I conjectured, since $ax+by=c$, by Bezout's Lemma $\gcd(a,b)=c$? If $\gcd(a,b)=c$, then $\gcd(a,bc)|c$ is $c|c$. So that doesn't do anything. This question is a bit challenging. Many thanks for the help.
The equation $ax+by=c$ is equivalent to $\frac{a}{(a,b)}x+\frac{b}{(a,b)}y=\frac{c}{(a,b)},$ so it suffices to treat the case where $a$ and $b$ are coprime.
Let the equation be $mx+ny=N$ where $m,n$ are positive integers such that $(m,n)=1.$ By Bezout's lemma, there exist integers $(x_0,y_0)$ such that $mx_0 +ny_0=N.$ The problem is that we don't know the signs of $x_0$ and $y_0.$ By the classification of all solutions to a linear Diophantine equation, all solutions are given by $(x_0-kn,y_0+km)$ over all integers $k.$
We want there to exist a unique integer $k$ such that $0\le x_0-kn<n.$ By the Euclidean division of $x_0$ by $n,$ there exists a unique non-negative remainder $x_1$ and a unique quotient $k$ such that $$x_0-kn=x_1,0\le x_1<n.$$ So $x_1$ is the unique solution that we seek. You can actually then show that the corresponding $y_1=y_0+qm$ is also non-negative, but since you did not ask for it, I'll leave that to you.