【数学】最大公约数gcd

2021-06-28 约 1424 字预计阅读 3 分钟

约数定义： 如果一个整数能被另一个整数整除,那么第二个整数就是第一个整数的约数。即$a%b==0$，且$(a!=0,b!=0)$，那么$b$是$a$的约数。

一个数字的约数是有限的，两数的最大公约数指两个数字最大的公有约数。

注意：

推论1： 如果$a$可以被$b$整除，如果$k$也是正整数，那么$ka$也可以被$b$整除。
推论2： 如果$a$可以被$c$整除，如果$b$也可以被$c$整除，那么$a±b$也能被$c$整除。
推论3： 如果$a$能被$b$整除，同时$b$也可以被$a$整除，则$a=b$。

推论3证明过程：
- 因为$a=qb,b=ta$
- 将$b$带入$a$的表达式得到$a=qt\cdot a$，得到$qt=1$
- 由于$q$和$t$都是正整数，因此$q=t=1$，有$a=b$

辗转相除法 ：输入两个数$x$和$y$。首先保证$x>y$；之后$x$除$y$得到了余数和结果。将上一个式子的除数赋值给被除数，将余数赋值给除数。终止条件为余数为0，最后的被除数就是$gcd(x,y)$。

证明： 已知两个数字：$m$和$n$，其中$m>n,m=n\cdot q+r$，求证$gcd(m,n)=gcd(n,r)$?

解答：因为$r=m-q*n$和$m$，$n$都有相同的公约数（推论1和2），最大公约数自然也都相同

设$a=gcd(m,n)$，$b=gcd(n,r)$
因为$m$、$n$能被$a$整除：
- 由推论1，$q\cdot n$也能被$a$整除
- 由推论2，$r=m-q\cdot n$也能被$a$整除
- 由于$n$和$r$都能被$a$整除，因此$a$一定也是$n$和$r$的最大公约数$b=gcd(n,r)$的约数
因为$n$，$r$能被$b$整除：
- 由推论1和推论2，$m=q\cdot n+r$一定能被$b$整除
- 由于$m$和$n$都能被$b$整除，那么二者的最大公约数$a=gcd(m,n)$也一定能被$b$整除
因为证出$a$能被$b$整除，且$b$也能被$a$整除；由推论3，得到$a=b$

# 辗转相除
def gcd1(x, y) -> int:
    (x, y) = (x, y) if x >= y else (y, x)
    return y if y == 0 or x % y == 0 else gcd1(y, x % y)

辗转相减法 ：输入两个数$x$和$y$；在保证被减数$x$大于减数$y$的情况下，不断循环$x-y$；将减数赋值给被减数，将结果赋值在减数。终止条件为$x=y$时，最大公约数就是$x=y=gcd(x,y)$就是最大公约数。

证明： 已知两个数字：$m$和$n$，其中$m>n,r=m-n$，求证$gcd(m,n)=gcd(n,r)$?

解答：因为$r=m-n$和$m$，$n$都有相同的公约数（推论2），最大公约数自然也都相同

# 辗转相减
def gcd2(x, y) -> int:
    (x, y) = (x, y) if x >= y else (y, x)
    return y if y == 0 or x == y else gcd2(y, x-y)

目录