Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Linear combination of two numbers

  1. Oct 29, 2012 #1
    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 [itex]\in[/itex] Z. Find x,y.
  2. jcsd
  3. Oct 29, 2012 #2

    1) Apply the euclidean algorithm to find the gcd

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


    $$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 [itex]\,2\cdot 24+(-3)\cdot 15=3\,[/itex]

  4. Oct 29, 2012 #3
    Ok, now I understand. Thanks a lot.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook