a,b是正整数,证明:若对于整数n,m,有ma+nb=1,则 gcd(a,b)=1.(即:a,b 最大公约是是1)
来源:学生作业帮助网 编辑:六六作业网 时间:2025/01/22 13:15:27
a,b是正整数,证明:若对于整数n,m,有ma+nb=1,则 gcd(a,b)=1.(即:a,b 最大公约是是1)
a,b是正整数,证明:若对于整数n,m,有ma+nb=1,则 gcd(a,b)=1.(即:a,b 最大公约是是1)
a,b是正整数,证明:若对于整数n,m,有ma+nb=1,则 gcd(a,b)=1.(即:a,b 最大公约是是1)
gcd(a,b)记为c,则有c|a,且c|b,从而c|ma+nb,即c|1;所以c=1
由辗转相除法和辗转相除法中的一个重要定理可知:存在整数s,t使得r=as+bt.其中r=(a,b)即:(a,b)=rs+bt.
由题意可知ma+nb=1,所以就有(a,b)=1.
反证法:
假设公约数gcd不等于1,为正整数k。
mkA+nkB=1
mA+nB=1/K
上式:左边整数,右边分数不成立!
定理:如果d是整数a,b的公约数,则d是ma + nb的约数(其中m,n是整数),且满足ma+nb形式的最小的正整数是a,b的最大公约数。
证明:
1)假设d是a,b的一个约数,d|a,d|b,集合S = { ma + nb | m,n ∈ Z},则对于S中任意一个元素x,有 x = k1a + k2b因此根据前面结论,d | x,也就是说d整除S中...
全部展开
定理:如果d是整数a,b的公约数,则d是ma + nb的约数(其中m,n是整数),且满足ma+nb形式的最小的正整数是a,b的最大公约数。
证明:
1)假设d是a,b的一个约数,d|a,d|b,集合S = { ma + nb | m,n ∈ Z},则对于S中任意一个元素x,有 x = k1a + k2b因此根据前面结论,d | x,也就是说d整除S中的每个元素。由此可以得出,S中的最小整数是a,b所有公约数的倍数。2)假设d是集合S中最小的正整数,则d能整除S中任何一个元素。反证:假设存在x∈S,d不能整除x,则x可以表示为 x = kd + r 其中r为小于d的正整数,由于x,d都是S的元素,因此都可以表示为ma+nb的形式,由上式可以得出 r = x - kd也可以表示为ma + nb的形式,因此r∈S,这于d是S中最小正整数矛盾。因此,d能整除S中任何一个元素。3) a和b都是S的元素,因为 a = 1 a + 0 b b = 0 a + 1 b因此2中所述的d必然能整除a,b,因此d是a,b的公约数。而根据1,a,b的所有约数都能整除d,因此d是最大公约数。
显然d=1时也成立
收起