Euclidean algorithm leverages multiplication and subtraction, which humans are fairly good at, to make fractions like 15996751/3870378 reducible. Also useful in scaling equations down to their simplest integer representation in one step, given with extra integers, GCD(C,GCD(A,B)) is equivalent to GCD(A,B,C). It's been around for over two thousand years and mathematicians have bent it to many purposes , but just the first bit should be justification.
I am trying to find the $\gcd$ of two numbers forming a linear combination: $5a+24b=1$. I know that $a = 5$ and $b = -1$, but I found these values through trial and error. How would I use Euclid's Algorithm to find a and b?
This is what I have done so far: $24/5 \implies Q=4, R=4, 5/4 \implies Q=1, R=4, 4/4 \implies Q=1, R=0$ How do I use this info to work backwards?
No comments:
Post a Comment