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
$\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.
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!