| Line 1: | Line 1: | ||
Any two nonzero integers <math>a</math> and <math>b</math> have a greatest common divisor, which can be expressed as the smallest positive linear combination of <math>a</math> and <math>b</math>. Moreover, an integer is a linear combination of <math>a</math> and <math>b</math> if and only if it is a multiple of their greatest common divisor. | Any two nonzero integers <math>a</math> and <math>b</math> have a greatest common divisor, which can be expressed as the smallest positive linear combination of <math>a</math> and <math>b</math>. Moreover, an integer is a linear combination of <math>a</math> and <math>b</math> if and only if it is a multiple of their greatest common divisor. | ||
| − | The greatest common divisor of two numbers can be computed by using a procedure known as the Euclidean algorithm. First, note that if <math>a</math> | + | The greatest common divisor of two numbers can be computed by using a procedure known as the Euclidean algorithm. First, note that if <math>a\neq\,\!0</math> and <math>b|a</math>, then gcd<math>(a,b)=|b|</math>. The next observation provides the basis for the Euclidean algorithm. If <math>a=bq+r</math>, then <math>(a,b)=(b,r)</math>. Thus given integers <math>a>b>0</math>, the Euclidean algorithm uses the division algorithm repeatedly to obtain |
<math>a=bq_{1}\!+r_{1}\!</math>, with <math>0\leq\,\!r_{1}\!<b</math><br> | <math>a=bq_{1}\!+r_{1}\!</math>, with <math>0\leq\,\!r_{1}\!<b</math><br> | ||
| − | <math>b=r_{1}\!q_{2}\!+r_{2}\!</math>, with <math>0\leq\,\! | + | <math>b=r_{1}\!q_{2}\!+r_{2}\!</math>, with <math>0\leq\,\!r_{2}\!<b</math> <br> |
etc. | etc. | ||
| − | Since <math> | + | Since <math>r_{1}\!>r_{2}\!>\ldots\,\!</math> , the remainders get smaller and smaller, and after a finite number of steps we obtain a remainder <math>r_{n+1}\!=0</math>. Thus, <math>\gcd\,\!(a,b)=\gcd\,\!(b,r_{1}\!)=\cdots\,\!=r_{n}\!</math>. |
Latest revision as of 19:42, 22 January 2009
Any two nonzero integers $ a $ and $ b $ have a greatest common divisor, which can be expressed as the smallest positive linear combination of $ a $ and $ b $. Moreover, an integer is a linear combination of $ a $ and $ b $ if and only if it is a multiple of their greatest common divisor.
The greatest common divisor of two numbers can be computed by using a procedure known as the Euclidean algorithm. First, note that if $ a\neq\,\!0 $ and $ b|a $, then gcd$ (a,b)=|b| $. The next observation provides the basis for the Euclidean algorithm. If $ a=bq+r $, then $ (a,b)=(b,r) $. Thus given integers $ a>b>0 $, the Euclidean algorithm uses the division algorithm repeatedly to obtain
$ a=bq_{1}\!+r_{1}\! $, with $ 0\leq\,\!r_{1}\!<b $
$ b=r_{1}\!q_{2}\!+r_{2}\! $, with $ 0\leq\,\!r_{2}\!<b $
etc.
Since $ r_{1}\!>r_{2}\!>\ldots\,\! $ , the remainders get smaller and smaller, and after a finite number of steps we obtain a remainder $ r_{n+1}\!=0 $. Thus, $ \gcd\,\!(a,b)=\gcd\,\!(b,r_{1}\!)=\cdots\,\!=r_{n}\! $.
