I am thinking about this in the context of the two water jugs problem. I know that a jug of capacity $n$ can be filled if $\gcd (a,b) \mid n.$ Does this have the corollary that any integer can be written as a linear combination of $a$ and $b$ if $\gcd (a,b) = 1?$


marked as duplicate by Jyrki Lahtonen, Lord Shark the Unknown, Namaste, John B, Cesareo Oct 22 '18 at 20:20

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Yes, that is right $\endgroup$ – DonAntonio Oct 21 '18 at 21:34
  • $\begingroup$ If $\gcd(a,b) = 1$ then there are $c,d $ such that $ac+bd = 1$ and hence if $p$ is an integer we can write $p = (cp)a + (dp)b$. $\endgroup$ – copper.hat Oct 21 '18 at 21:36

Yes that's a consequence of Bézout's identity which can be proved by Euclidean algorithm and which states that

$$\forall a,b\in \mathbb{Z}\quad \gcd(a,b)=1 \iff \exists x,y\in \mathbb{Z}\quad ax+by=1$$

from which we obtain that

$$a\cdot nx+b\cdot ny=n$$

  • $\begingroup$ @copper.hat Thanks for the editing, the fact is that I've also encountered that as "Bezout's theorem" but "Bezout's identity" seems to be the official name. $\endgroup$ – gimusi Oct 21 '18 at 21:40
  • 1
    $\begingroup$ Bézout's theorem is usually interpreted in the context of algebraic geometry, $\endgroup$ – copper.hat Oct 21 '18 at 21:41
  • $\begingroup$ @copper.hat Indeed I'm completely unaware about algebraic geometry :) $\endgroup$ – gimusi Oct 21 '18 at 21:43
  • $\begingroup$ Thank you very much! $\endgroup$ – taurus Oct 21 '18 at 21:45

In general, if $d=\gcd(a,b)$, then any integer of the form $nd$ for some integer $n$ can be expressed as a linear combination of $a$ and $b$. This is because we can write $a=da_1$ and $b=db_1$ for integers $a_1,b_1$ so that $\gcd(a_1,b_1)=1$. By the euclidean algorithm this leads us to the fact that there exists $k_1,k_2$ such that $$1=k_1a_1+k_2b_1$$ for all $a_1,b_1$. Multiplying both sides of the equation by $nd$, we get $$nd=nk_1(da_1)+nk_2(db_1)=nk_1a+nk_2b$$ Which gives us a way to find anything of the form $nd$ as a linear combination of $a,b$.


Not the answer you're looking for? Browse other questions tagged or ask your own question.