关于欧几里得算法中的完全商q_(n+1)的一个注记  

A note on complete quotient q_(n+1) in euclidean algorithm

作　　者：刘古胜[1] 

机构地区：[1]荆楚理工学院数理系,湖北荆门448200

出　　处：《高师理科学刊》2008年第3期14-15,共2页Journal of Science of Teachers＇College and University

摘　　要：利用欧几里得辗转相除法可以计算任意2个整数a,b的最大公约数(a,b),通过[a,b]=(ab/a,b)可以求得a,b的最小公倍数[a,b].利用欧几里得辗转相除法中的不完全商qk(k=1,2,…,n)和完全商qn+1,借助递推关系:P0=1,P1=q1,Pk=qk Pk-1+Pk-2,Q0=0,Q1=1,Qk=qkQk-1+Qk-2(k=1,2,…,n,n+1),给出定理:若a,b是任意2个正整数,则[a,b]=Pn+1b=Qn+1a,并给出一种求a,b的最小公倍数的新方法.For two integers a, b, one can calculate the greatest common divisor （a, b） of a and b by using Euclidean algorithm, then the least common multiple [a, b] =ab（a,b）Given a new algorithm[a, b] = P,,＋lb = Q.＋laby using the relation Po = 1, Pl = ql, Pk = qkPk-l ＋ Pk-2 Qo = O, Ql = 1, Qk = qkQk-1 ＋ Qk-2 （k = 1, 2, ……, n, n ＋ 1） where qk （k = 1, 2, ……, n）, qn＋1 is incomplete quotient and complete quotient in Euclidean algorithm, respectively.

关 键 词：欧几里得算法 最大公约数 最小公倍数 商 

分 类 号：O156.1[理学—数学]