Question

后天有初等数论的考试，请教一个问题 设m,n为正整数且m为奇数，证明：若a为偶数，则a^m-1与a^+1互素 谢谢！

Answer 1

设m=kn+r, r<n (a^m-1, a^n+1)=(a^n^k*a^r -1, a^n +1)
=((-1)^k*a^r -1, a^n+1)
=(a^r-(-1)^k, a^n+1)
设n=qr+s, s<r =(a^r-(-1)^k, (-1)^(kq)*a^s+1)
=(a^r-(-1)^k, a^s+(-1)^(kq))
继续下去。。。。。。。。。。。　＝(a^(m,n)+(-1)^x, a^[k*(m,n)]+(-1)^y）
=(a^(m,n)+(-1)^x, (-1)^y +(-1)^z)

设(m,n)=w m=uw n=vw则 =(a^wu-1, a^wv+1)
设b=a^w =(b^u-1,b^v+1)
=(b+(-1)^x, (-1)^y +(-1)^z)
　　　　　　　　　　　　　　=b+(-1)^x或者1（注意b是偶数）
下面分析b+(-1)^x>1（注意是奇数，最小是3）时,　b+(-1)^x不可能是公约数。
如果x是奇数，则a^n+1 =b^v+1=k*(b-1)+2　显然公约数不是b-1，所以只能是1。
如果x是偶数，则a^m-1=b^u-1=k(b+1)+(-1)^u-1=k(b+1)-2　　注意u是奇数
显然公约数不是b+1，所以只能是1
因此公约数最终只可能是1,　........互素。

延伸一下，如果想得到公约数b+(-1)^x　>2
a^m-(-1)^A=k(b+(-1)^x)+[-(-1)^x]^u-(-1)^A＝k(b+(-1)^x) +(-1)^u^(x+1) -(-1)^A]
a^n-(-1)^B=k(b+(-1)^x)+[-(-1)^x]^v-(-1)^B＝k(b+(-1)^x) +(-1)^v^(x+1) -(-1)^B]
u是偶数，A=u
u是奇数，A与x+1同奇偶 x是偶数，则A是奇数＝u;　x是奇数，A是偶数，(b-1)|b^u-1
x是偶数则A＝u=m/(m,n)，B＝v=n/(m,n)即可
x是奇数则A＝B＝2即可

综合起来即：（a^m-1, a^n-1)=a^(m,n) -1
　　　　(a^m-(-1)^[m/(m,n)], b^n-(-1)^[n/(m,n)]=a^(m,n) +1
　　　　　其它情况(a^m+(-1)^x, a^n+(-1)^y) =：a是偶数，则＝1；a是奇数，则＝2