当前位置:首页>维修大全>综合>

初等数论求最大公因数例题(最大公因数的最简单方法)

初等数论求最大公因数例题(最大公因数的最简单方法)

更新时间:2024-02-07 11:52:03

初等数论求最大公因数例题

最大公因数,指两个或多个整数共有约数中最大的一个。以下是一个用辗转相除法求最大公因数的例子:

 

求18和24的最大公因数。

 

用较大数除以较小数得到商和余数:

 

24div18=1ldots6,其中6是余数。

 

再用除数和余数做除法运算:

 

18div6=3,余数为0。

 

当余数为0时,此时的除数6就是原来两个数的最大公因数。

 

因此,18和24的最大公因数是6。

 

辗转相除法是求最大公因数的一种算法,它的原理是:用较大数除以较小数得到商和余数,再用除数和余数做除法运算,当余数为0时,此时的除数就是原来两个数的最大公因数。

一、定义

定义:给定两个整数a,b,必有公共的因数,叫做它们的公因数,当a,b不全部为0时,在有限个公因数中最大的那个叫做a、b的最大公因数,记作(a,b)

二、一种方法——辗转相除法

描述:设a,b为任意两个整数,且b不为0,应用带余除法,以b除a,得到商q1,余数r1;如果余数r1不为0,以r1除b,得到商q2,余数r2;如果r2不等于0,以r2除r1,如此继续下去,在有限个除法后,必然得到rn不为0且整除rn-1。

三、最大公约数的性质

关于最大公约数有一条重要的性质,这条性质在求解一次同余方程和不定方程时经常遇到。

1)

证明:不妨设b>0,用b除a,则有a = b*q1 + r1,

若r1 = 0,(a,b) = (b,r1) = b;所以(a,b) = a * 0 + b * 1

若r1 != 0,用r1除b;b = r1 * q2 + r2,

  若r2 = 0,(a,b) = (b,r1) = (r1,r2) = r1 = a - b * q1;所以(a,b) = a * 0 + b * (-q1)

  若r2 != 0,用r2 除r1;r1 = r2 * q3 + r3.

    若r3 = 0,(a,b) = (r2,r3) = r2 = b - r1 * q2 = b - (a - b * q1) * q2;所以(a,b) = a * (-q2) + b * (1 + q1 * q2)

    若r3 != 0,用r3 除r2........

由于最大公因数一定存在,所以一定可以经过有限次 得到rn = 0,所以这样的m,n一定存在且可以求出来。

2)由上面那条性质,可以推出整数的一条性质

证明:因为(a,b) = 1,所以存在整数m,n,使得am + bn = (a,b) = 1,

  于是(ac)m + (bc)m = c

  因为a | ac,a | bc,所以a | (ac)m + (bc)m,即a | c

更多栏目