# If $\gcd (a,b) = 1,$ can any integer be written as a linear combination of $a,b?$ [duplicate]

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, amWhy, John B, CesareoOct 22 at 20:20

• Yes, that is right – DonAntonio Oct 21 at 21:34
• 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$. – copper.hat Oct 21 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$$

• @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. – gimusi Oct 21 at 21:40
• Bézout's theorem is usually interpreted in the context of algebraic geometry, – copper.hat Oct 21 at 21:41
• @copper.hat Indeed I'm completely unaware about algebraic geometry :) – gimusi Oct 21 at 21:43
• Thank you very much! – taurus Oct 21 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$$.