Linear combinations?

Printable View

February 13th 2006, 02:47 AM
eroz

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?
February 13th 2006, 02:24 PM
ThePerfectHacker

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.
February 26th 2006, 08:35 AM
SkyWatcher

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!
February 26th 2006, 11:52 PM
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!
February 27th 2006, 04:20 PM
ThePerfectHacker

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.