「初等数论初步」最大公因数

发表于 | 分类于

最大公因数：当a，b不全为0时，再有限个公因数中最大的一个叫做a，b的最大公因数，记作（a,b）

如果a，b的最大公因数为1，那么称a，b是互素的

辗转相除法求最大公因数：
问题：如果b除a的余数为r，那么（a,b）是否等于（b,r）？

事实上 ，如果d为a，b的公因数，即d|a，d|b，则d|（a-bq=r），从而d为b,r的公因数，同理可证，r,b是a,b的最大公因数.因此，a,b的的公因数的集合与r,b的公因数集合相同，从而它们的最大公因数相等，即（a,b） = （b,r）.利用这种思想求解最大公约数，就是辗转相除法的思想.

上代码：

1
2
3
4
5
int gcd(int a,int b)
{
    if(a % b == 0) return b;
    else return gcd(b, a % b);
}

判断两个数是否互素（互质）
代码：

1
2
3
4
5
6
7
8
9
10
11
bool prime(int a, int b) {
	int t;
    if(a < b) {
        std::swap(a, b);
    }
    while(a % b){
        t = b; b = a % b; a = t;
    }
    if(b > 1) return false;
    else if(b == 1) return true;
}