Linear combination of two numbers

[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.

 

[DonAntonio]

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.

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

 

[pyfgcr]

Ok, now I understand. Thanks a lot.