辗转相除法的讲解初等数论.pptVIP

初等数论 Number Theory 第一章 整除理论 整除性理论是初等数论的基础。本章要介绍带余数除法，辗转相除法，最大公约数，最小公倍数，算术基本定理以及它们的一些应用。 第五节 辗转相除法 本节要介绍一个计算最大公约数的算法——辗转相除法，又称Euclid算法。它是数论中的一个重要方法，在其他数学分支中也有广泛的应用。 第五节 辗转相除法 定义1 下面的一组带余数除法,称为辗转相除法. 设a和b是整数, b ? 0, 依次做带余数除法： a = bq1 ? r1， 0 r1 |b|， b = r1q2 ? r2， 0 r2 r1 ，… … rk ? 1 = rkqk + 1 ? rk + 1, 0 rk + 1 rk ， (1) … … rn ? 2 = rn ? 1qn ? rn， 0 rn rn-1 ， rn ? 1 = rnqn + 1 . 由于b是固定的，而且|b| r1 r2 … ， 所以式(1)中只包含有限个等式。 第五节 辗转相除法 下面，我们要对式(1)所包含的等式的个数，即要做的带余数除法的次数进行估计。 引理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成立。 证毕。 第五节 辗转相除法 定理1 (Lame) 设a, b?N，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， 第五节 辗转相除法 此时由式(1)得到 aQ2 ? bP2 = aq2 ? b(q2q1 ? 1) = (a ? bq1)q2 ? b = r1q2 ? b = ?r2， 即式(3)成立。 第五节 辗转相除法 假设对于k m（1 ? m ? n）式(3)成立，由此假设及式(1)得到 aQm?bPm=a(qmQm ?1?Qm ?2) ?b(qmPm ?1 ? Pm ?2) = (aQm ? 1 ? bPm ? 1)qm ? (aQm ? 2 ? bPm ? 2) = (?1)m ? 2rm ? 1qm ? (?1)m ? 3rm ? 2 = (?1)m ? 1(rm ? 2 ? rm ? 1qm) = (?1)m? 1rm ， 即式(3)当k = m时也成立。定理由归纳法得证。 证毕。 第五节 辗转相除法 定理3 使用式(1)中的记号，有rn = (a, b). 证明 由第三节定理1，从式(1)可见 rn = (rn ? 1, rn) = (rn ? 2, rn ? 1) = … = (r1, r2) = (b