# Find a specific solution to a linear Diophantine equation

Prove that for any given integers $$b > a \geq 1$$ there exists an integer solution $$u$$, $$w$$ to $$au - bw = \text{gcd}(a,b)$$ with $$0\leq u\leq b-1$$ and $$0\leq w \leq a-1$$.

This is supposedly a simple exercice in applying the Euclidean division. I tried a lot of things but my technique is mainly starting with any solution $$m,n\in\mathbb{Z}$$ such that $$am-bn=(a,b)$$ and then setting $$m=qb+u$$ for some $$q,u\in\mathbb{Z}$$ with the constraint that $$0\leq u\leq b-1$$. Then, by substitution, I get

$$\begin{equation*} a(qb+u) - bn = au - b(n - qa) = (a,b) \end{equation*}$$

I don't know what is the best way to proceed here. Do I need to show that $$0\leq n-qa\leq a-1$$? It seems to me that there must be some quick and elegant way to do this, but I've been playing with inequalities for hours and nothing seems to work.

Am I on the right track or did I miss something important? I'm trying to see a pattern here.

• Suppose you already got your $0 \leq u \leq b-1$. Then $w = \frac{au - \gcd(a,b)}{b}$. From the constrain on $u$ you get $-\frac{\gcd(a,b)}{b} \leq w \leq \frac{ab - a - \gcd(a,b)}{b}$. Recall that from your assumption, $b > a \geq \gcd(a,b)$. – Hw Chu Oct 26 '18 at 17:36
• I am sorry, I do not understand why $b>a\geq \text{gcd}(a,b) \Rightarrow 0\leq w\leq a-1$ from the inequality you wrote. – malloc19 Oct 26 '18 at 17:57
• Let us look at the simpler side $w \geq 0$. Since $w$ is an integer, so if you can prove $w > -1$ then it is equivalent to $w \geq 0$. To show $w > -1$ it is enough to show that $-\frac{\gcd(a,b)}{b} > -1$, equivalently $\gcd(a,b)<b$. – Hw Chu Oct 26 '18 at 18:16
• I see, thank you. Can you help me with the other side of the inequality? I fail to see it. – malloc19 Oct 26 '18 at 20:14