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.

  • $\begingroup$ 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)$. $\endgroup$ – Hw Chu Oct 26 '18 at 17:36
  • $\begingroup$ 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. $\endgroup$ – malloc19 Oct 26 '18 at 17:57
  • $\begingroup$ 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$. $\endgroup$ – Hw Chu Oct 26 '18 at 18:16
  • $\begingroup$ I see, thank you. Can you help me with the other side of the inequality? I fail to see it. $\endgroup$ – malloc19 Oct 26 '18 at 20:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.