Results 1 to 5 of 5

Math Help - Linear combinations?

  1. #1
    Newbie
    Joined
    Jan 2006
    Posts
    6

    Linear combinations?

    I couldn't find the english word for "linear combination" so i hope there is such a word and that you understand what i mean.

    Write gcd(4774,6851) = 31 as a linear combination of 4774 & 6851

    That's 31 = 4774*s + 6851*t

    How do i get s & t?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by eroz
    I couldn't find the english word for "linear combination" so i hope there is such a word and that you understand what i mean.

    Write gcd(4774,6851) = 31 as a linear combination of 4774 & 6851

    That's 31 = 4774*s + 6851*t

    How do i get s & t?
    I did this using finite countinued fractions. One such combination for
    4774x+6851y=31 is,
    (x,y)=(-33,23).

    Assuming you studied countinued fractions,
    Explanation :
    Using the Euclid Algorithm we find \gcd(4774,6851).
    Thus, the countinued fraction for 4474/6851 is:
    [0;1,2,3,2,1,6]
    Now using the identity that,
    p_kq_{k-1}-q_kp_{k-1}=(-1)^{k-1}\gcd
    where q_k,p_k are convergents.
    Thus,
    4774(33)-6851(23)=-31
    Now manipulate the signs
    Q.E.D.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jan 2006
    Posts
    56
    Quote Originally Posted by eroz
    I couldn't find the english word for "linear combination" so i hope there is such a word and that you understand what i mean.

    Write gcd(4774,6851) = 31 as a linear combination of 4774 & 6851

    That's 31 = 4774*s + 6851*t

    How do i get s & t?
    i dont understand quite wright your question:
    (for me the "equation" gcd(4774,6851)=31 means (what it means) that 31 is the greatest integer that devides both number, witch is true: 4774=154*31
    6857=221*31 and 221 is probably prime (whith 154)

    so this equality means something (see above)
    in the other hand (there is s an t for witch) 31=4774*s+ 6851*t means something else (it mean what it mean (if you see whath i mean))!
    you surely know the "Bezout identity" that "says" that for any couple of number prime mutualy (154,221) for example there is a (an infinity of) couple of integer (a,b) for witch a*154+b*221=1
    i dont remenber the algorithm to find those number (look at Bezout in an encyclopeadia(maybe))
    and you would have to multiply the result by any number (31) to find a linear combination of mutualy prime number that gives the same number
    That is if i assumed you don't know continuous fraction notation!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Jan 2006
    Posts
    6
    Yeah i understand what you mean! I got help from my lecturer so it's ok now. We are using euclid's algorithm backwards for this problem!

    Thanks anyway for the help!
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by eroz
    Yeah i understand what you mean! I got help from my lecturer so it's ok now. We are using euclid's algorithm backwards for this problem!

    Thanks anyway for the help!
    Using the Euclidean Algorithm backwards is the other method. I just happen to think that a countinued fraction works simpler.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. linear combinations
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: April 12th 2011, 01:53 PM
  2. Linear Combinations
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: October 1st 2010, 03:36 AM
  3. [SOLVED] Linear combinations
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: July 22nd 2010, 07:34 AM
  4. Linear combinations
    Posted in the Differential Equations Forum
    Replies: 2
    Last Post: May 6th 2009, 05:04 PM
  5. linear combinations
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: March 10th 2009, 06:49 AM

Search Tags


/mathhelpforum @mathhelpforum