1、初等数论Number Theory第一章 整除理论 整除性理论是初等数论的基础。本章要介绍带余数除法，辗转相除法，最大公约数，最小公倍数，算术基本定理以及它们的一些应用。第五节 辗转相除法 本节要介绍一个计算最大公约数的算法 辗转相除法，又称 Euclid算法。它是数论中的一个重要方法，在其他数学分支中也有广泛的应用。第五节 辗转相除法定义 1 下面的一组带余数除法 ,称为辗转相除法 .设 a和 b是整数 , b 0, 依次做带余数除法：a = bq1 r1， 0 r1 r2 ，所以式 (1)中只包含有限个等式。第五节 辗转相除法下面，我们要对式 (1)所包含的等式的个数，即要做的带余数除法的
2、次数进行估计。引理 1 用下面的方式定义 Fibonacci数列 Fn：F1 = F2 = 1， Fn = Fn 1 Fn 2， n 3，那么对于任意的整数 n 3，有Fn n 2， (2)其中第五节 辗转相除法证明 容易验证 2 = 1。当 n = 3时，由F3 = 2 = 可知式 (2)成立。假设式 (2)对于所有的整数 k n（ n 3）成立，即Fk k 2， k n，则第五节 辗转相除法Fn + 1 = Fn Fn 1 n 2 n 3 = n 3( 1) = n 3 2 = n 1，即当 k = n 1时 式 (2)也成立。由 归纳 法知式 (2)对 一切 n 3成立。证毕 。 第五节
3、 辗转相除法定理 1 (Lame) 设 a, bN， a b，使用在式 (1)中的记号，则n 5log10b. 证明 在式 (1)中， rn 1， qn + 1 2， qi 1（ 1 i n），因此rn 1 = F2 ，rn 1 2rn 2 = F3 ，第五节 辗转相除法rn 2 rn 1 rn F3 F2 = F4 ， b r1 r2 Fn + 1 Fn = Fn + 2 ，由此及式 (2)得b n = ，即log10b nlog10 ，这 就是定理 结论 。 证毕 。第五节 辗转相除法定理 2 使用式 (1)中的记号，记P0 =1， P1 =q1， Pk =qkPk 1 Pk 2， k 2，Q0 =0， Q1 =1， Qk =qkQk 1 Qk 2， k 2，则aQk bPk = (1)k 1rk， k = 1, 2, , n . (3)证明 当 k = 1时，式 (3)成立。当 k = 2时，有Q2 = q2Q1 Q0 = q2， P2 = q2P1 P0 = q2q1 1，
