怎么证明如果2的n次方减1是质数,证明n是质数.(反过来怎么证明?)另外,如何证明gcd(a,b,c)=gcd(gcd(a,b),c)
来源：学生作业帮助网 编辑：六六作业网 时间：2024/11/22 09:48:10
怎么证明如果2的n次方减1是质数,证明n是质数.(反过来怎么证明?)另外,如何证明gcd(a,b,c)=gcd(gcd(a,b),c)
怎么证明如果2的n次方减1是质数,证明n是质数.(反过来怎么证明?)
另外,如何证明gcd(a,b,c)=gcd(gcd(a,b),c)
怎么证明如果2的n次方减1是质数,证明n是质数.(反过来怎么证明?)另外,如何证明gcd(a,b,c)=gcd(gcd(a,b),c)
用反证法可以证明如果2的n次方减1是质数,则n必是质数.
假设n不是质数,则必存在大于1的数a,b,有n=ab,于是
2^n-1=2^(ab)-1=(2^a-1)(2^(a-1)+2^(a-2)b+...+2^(b-1)),这与2^n-1是质数矛盾.
反过来怎么证明?,反过来不正确,即n是质数,2^n-1不一定是质数,举一反例,n=11是质数,但
2^11-1=2047＝23×89
不是质数.
gcd(a,b,c)是a,b,c的公约数,故gcd(a,b,c)能整除a,b,c,由于gcd(a,b,c)也是a,b的公约数,gcd(a,b)是a,b的最大公约数,故gcd(a,b,c)能整除gcd(a,b),gcd(a,b,c)又能整除c,故gcd(a,b,c)是 gcd(a,b)和c的公约数,gcd(gcd(a,b),c)是gcd(a,b)和c的最大公约数,于是gcd(a,b,c)能整除gcd(gcd(a,b),c).
gcd(gcd(a,b),c) 是gcd(a,b)和c的公约数,故gcd(gcd(a,b),c) 能整除gcd(a,b)和c,由gcd(a,b)是a,b的公约数,故gcd(gcd(a,b),c) 也能整除a,b,故gcd(gcd(a,b),c)是a,b,c的公约数,又gcd(a,b,c)是a,b,c的最大公约数,故gcd(gcd(a,b),c) 能整除gcd(a,b,c).
gcd(a,b,c)和gcd(gcd(a,b),c)互相能整除,故gcd(a,b,c)=gcd(gcd(a,b),c).
因为2的n次方都为偶数 又因为偶数减1都为奇数 所以2的n次方减1都为奇数
2^ab-1必有2^a-1和2^b-1因子(a,b为>1正整数)