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?

Printable View

- Feb 13th 2006, 02:47 AMerozLinear 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? - Feb 13th 2006, 02:24 PMThePerfectHackerQuote:

Originally Posted by**eroz**

$\displaystyle 4774x+6851y=31$ is,

$\displaystyle (x,y)=(-33,23)$.

Assuming you studied countinued fractions,

Explanation :

Using the Euclid Algorithm we find $\displaystyle \gcd(4774,6851)$.

Thus, the countinued fraction for $\displaystyle 4474/6851$ is:

$\displaystyle [0;1,2,3,2,1,6]$

Now using the identity that,

$\displaystyle p_kq_{k-1}-q_kp_{k-1}=(-1)^{k-1}\gcd$

where $\displaystyle q_k,p_k$ are convergents.

Thus,

$\displaystyle 4774(33)-6851(23)=-31$

Now manipulate the signs

Q.E.D. - Feb 26th 2006, 08:35 AMSkyWatcherQuote:

Originally Posted by**eroz**

(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! - Feb 26th 2006, 11:52 PMeroz
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! - Feb 27th 2006, 04:20 PMThePerfectHackerQuote:

Originally Posted by**eroz**