# gcd

• Aug 10th 2007, 08:25 AM
shilz222
gcd
Why is it as a consequence of the Euclidean Algorithm that \$\displaystyle (a,b) = ax + by \$?

I know we start off with \$\displaystyle r_n = r_{n-2} - q_{n}r_{n-1} \$. From here do we solve for \$\displaystyle r_{n-2} \$ and \$\displaystyle r_{n-1} \$ in terms of the previous remainders eventually solving for \$\displaystyle r_n \$ in terms of \$\displaystyle a,b \$?

Thanks
• Aug 10th 2007, 09:28 AM
topsquark
Quote:

Originally Posted by shilz222
Why is it as a consequence of the Euclidean Algorithm that \$\displaystyle (a,b) = ax + by \$?

I know we start off with \$\displaystyle r_n = r_{n-2} - q_{n}r_{n-1} \$. From here do we solve for \$\displaystyle r_{n-2} \$ and \$\displaystyle r_{n-1} \$ in terms of the previous remainders eventually solving for \$\displaystyle r_n \$ in terms of \$\displaystyle a,b \$?

Thanks

Are you asking for why or just an example of how to use it?

If you are asking for the why of it, basically it's because of the division algorithm, and the fact that products and sums of integers are integers.

For an example, consider 45 and 63:
63 = 1 * 45 + 18
45 = 2 * 18 + 9
18 = 2 * 9 + 0

Thus (45, 63) = 9

-Dan