Question

证明:若m和n互素,则2^m-1和2^n-1也互素

Answer 1

首先你得知道，若a,b是正整数，那么存在正整数c,d，使得(a,b)=ac-bd。其中(a,b)表示a b的最大公约数
利用这个结论，那么存在正整数c,d，使得(2m,n)=2m*c-n*d
现在假设题目不成立，即存在质数p使得p|(2^m+1)和(2^n-1)。显然p是奇数
那么p|(2^(2mc)-1)和(2^(nd)-1).所以p|这俩的差=2^(nd)(2^(2mc-nd)-1)
于是p|(2^(2mc-nd)-1)。即p|2^((2m,n)-1)
但由n是奇数知(2m,n)=(m,n)。所以上式就是p|2^((m,n)-1)
又(m,n)|m。所以p|(2^m-1)。这与p|(2^m+1)矛盾！