# Linear combination of two numbers

1. Oct 29, 2012

### pyfgcr

I wonder how to find linear combination of 2 numbers, that is: ax+by=t, with t=m*GCD(a,b), and m,a,b $\in$ Z. Find x,y.

2. Oct 29, 2012

### DonAntonio

1) Apply the euclidean algorithm to find the gcd

2) After you finish 1, go BACK and get your expression

Example:

gcd(24,15)=3\Longrightarrow \begin{align*}24=&1\cdot 15+9\\15=&1\cdot 9+6\\9=&1\cdot 6+3\\6=&2\cdot 3\end{align*}

We know go back on the above algorithm (from the last line with a non-zero residue):

$$3=9-6=9-(15-9)=2\cdot 9-15=2(24-15)-15=2\cdot 24+(-3)\cdot 15$$

and thus $\,2\cdot 24+(-3)\cdot 15=3\,$

DonAntonio

3. Oct 29, 2012

### pyfgcr

Ok, now I understand. Thanks a lot.