用反證法可以證明如果2的n次方減1是質(zhì)數(shù),則n必是質(zhì)數(shù).
假設(shè)n不是質(zhì)數(shù),則必存在大于1的數(shù)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是質(zhì)數(shù)矛盾.
反過(guò)來(lái)怎么證明?,反過(guò)來(lái)不正確,即n是質(zhì)數(shù),2^n-1不一定是質(zhì)數(shù),舉一反例,n=11是質(zhì)數(shù),但
2^11-1=2047＝23×89
不是質(zhì)數(shù).
gcd(a,b,c)是a,b,c的公約數(shù),故gcd(a,b,c)能整除a,b,c,由于gcd(a,b,c)也是a,b的公約數(shù),gcd(a,b)是a,b的最大公約數(shù),故gcd(a,b,c)能整除gcd(a,b),gcd(a,b,c)又能整除c,故gcd(a,b,c)是 gcd(a,b)和c的公約數(shù),gcd(gcd(a,b),c)是gcd(a,b)和c的最大公約數(shù),于是gcd(a,b,c)能整除gcd(gcd(a,b),c).
gcd(gcd(a,b),c) 是gcd(a,b)和c的公約數(shù),故gcd(gcd(a,b),c) 能整除gcd(a,b)和c,由gcd(a,b)是a,b的公約數(shù),故gcd(gcd(a,b),c) 也能整除a,b,故gcd(gcd(a,b),c)是a,b,c的公約數(shù),又gcd(a,b,c)是a,b,c的最大公約數(shù),故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).