a,b是正整数,证明:若对于整数n,m,有ma+nb=1,则 gcd(a,b)=1.(即:a,b 最大公约是是1)

来源:学生作业帮助网 编辑:作业帮 时间:2024/05/03 12:03:28
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)

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时也成立

收起

a,b是正整数,证明:若对于整数n,m,有ma+nb=1,则 gcd(a,b)=1.(即:a,b 最大公约是是1) 一道数论题,对于x=(k*1+c)*(k*2+c)*……*(k*n+c) ,k是正整数,n大于等于2,也是正整数,c是大于等于0的整数,证明:x不是一个正整数的m次方(m取任意大于1的正整数)即x不=a^m 求一些数论题1.设n是正整数,证明6| n(n + 1)(2n + 1).2.证明:设m,n为整数,求证m+n,m-n与mn中一定有一个是3的倍数.3.证明:若n为自然数,求证9n+18n+9(mod 64).4.证明:若x对模m的指数是ab,a>0,b>0,则对 a,b是整数,若对所有正整数n,(2^n)a+b为完全平方数,证明:a=0 关于可逆矩阵的证明问题设P是n阶可逆矩阵,如果B=p^(-1)AP,证明:B^m=P^(-1)A^mP,这里m为任意整数.m是正整数 设集合M={x/x=3m+1,m是整数},N={y/y=3n+2,n是整数},若a,b是正整数,则ab与集合M,N的关系是什么? 求一道质数证明题对于正整数a和和另外一个大于1的整数n证明如果a^n-1是质数那么a=2 n是质数(提示:因数a^n-1) 证明题:a,b是整数,n是正整数,如果a的n次方整除b的n次方,则a整除b. 数学证明题:m,n都是正整数,且m,n都是两个正整数的完全平方和m,n都是正整数,且m,n都是两个正整数的完全平方和(就是m=a^2+b^2,n=c^2+d^2,a,b,c,d是正整数)如何证明m乘n,即mn也是两个正整数的完全平方 对于点集合A={(x,y)lx=m,y=-3x+2,m∈正整数},B={(x,y)lx=n,y=a(x^2-x+1),a∈整数n∈正整数},是否存在非零整数a,使得A∩B=空集?若存在,请求出a的值;若不存在,请说明原因. 用数学归纳法证明a^(n+1)|((a+1)^b+1)已知a,b是正整数,n为非负整数,a^n|b,证明a^(n+1)|((a+1)^b+1)应该是a^(n+1)|((a+1)^b-1) 证明:存在无穷多的正整数(m,n),使得(n+1)/m+(m+1)/n是一个整数 19.已知m,n都是正整数,且4m/(6m-3n) 是整数.若m/n 的最大值是a,最小值是b,则a+b=____________________ 证明:4/1(m*m+n*n-m-n)必为整数..m,n都是正整数... 已知组合数Cmn是正整数,证明:当n是正整数,m是非零自然数时,Cmn是整数 求助几道数论题1.设n是正整数,证明6| n(n + 1)(2n + 1).2.证明:设m,n为整数,求证m+n,m-n与mn中一定有一个是3的倍数.3.证明:若n为自然数,求证9n+18n+9(mod 64).4.证明:若x对模m的指数是ab,a>0 证明:若lima^n=a,则lima^(m+n)=a(其中m是固定的正整数^是脚标 一道数学命题证明若a^m=b^n,且a,b,m,n都为正整数,m,n互质,求证命题“必存在正整数t,使a=t^n,b=t^m的真假