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 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 forOriginally Posted by eroz
is,
.
Assuming you studied countinued fractions,
Explanation :
Using the Euclid Algorithm we find .
Thus, the countinued fraction for is:
Now using the identity that,
where are convergents.
Thus,
Now manipulate the signs
Q.E.D.
i dont understand quite wright your question: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!