本节介绍一个计算最大公因数的算法—辗转相除 法，又称EucI id算法，它是数论中的一个重要方法。 辗转相除法给定两个正整数 4,>41,用带 余除法得到下面的k+1个等式 =qo4+2, 0<2<41 4=912+43, 0<W3<2 2=9243+u4, 0<u4< 。 uk-1=gk-uk +uki1 0<uk<uk uk gkuk+ 不难看出 (4,h)=(4,4)=(42,4)=.=(u4,4k+1)=4k+本节介绍一个计算最大公因数的算法——辗转相除 法，又称Euclid算法，它是数论中的一个重要方法。 • 辗转相除法 给定两个正整数 ，用带 余除法得到下面的k+1个等式 0 1 u u  0 0 1 2 2 1 u q u u u u = +   , 0 1 1 2 3 3 2 u q u u u u = +   , 0 2 2 3 4 4 3 u q u u u u = +   , 0 . . 1 1 1 1 , 0 k k k k k k u q u u u u − − + + = +   k k k 1 u q u = + 不难看出 (u u u u u u u u u 0 1 1 2 2 3 1 1 , , , , ) = = = = = ( ) ( ) ( k k k + + )