多个正整数的最大公因数与最小公倍数的几个计算关系

Several Calculation Relationships between the Greatest Common Divisor and the Least Common Multiple

熟知对任意正整数a,b,c,有[a,b]=ab/(a,b),[(a,c),(b,c)]=([a,b],c),其中[],()分别表示最小公倍数和最大公因数.在RSA公钥算法中涉及两个正整数的最小公倍数和最大公因数的相关计算.为了给传统的RSA算法提供可能的优化方案,利用初等的方法与技巧,对任意多个正整数的最大公因数和最小公倍数的计算关系做了相关探究,推广了上述结果,给出了任意多个正整数的最大公因数和最小公倍数之间的3种计算关系.

It’s well-known that for any positive integers a,b,c,[a,b]=ab/(a,b),[(a,c),(b,c)]=([a,b],c),where[]and()represent the least common divisor and the greatest multiply,respectively.The RSA algorithm involved the re-lated calculation of the greatest common divisor and the least common multiple.In order to provide a possible optimiza-tion scheme for the traditional RSA algorithm,the present paper takes advantage of the elementary methods and skills to explore the calculation relationship between the greatest common divisor and the least common multiple of any positive integers.The result mentioned above is promoted to obtain three calculation relationships between the greatest common divisor and the least common multiple of any positive integers.