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

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

    DonAntonio
     
  4. Oct 29, 2012 #3
    Ok, now I understand. Thanks a lot.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Linear combination of two numbers
  1. Linear Combinations (Replies: 2)

  2. Linear combinations (Replies: 2)

  3. Linear combination (Replies: 1)

  4. Linear Combination (Replies: 2)

Loading...