Q:
m為大於1的整數, 證明: 2^m-1 不可能是m的倍數
-------------------------------------------
嗯...我知道我的敘述怪怪的= =..
不過我打不出"不整除"的符號...哈哈
有興趣的人試試看吧~!
-------------------------------------------
提示: 可以先證明下面的引理
m,n是正整數,證明: ( 2^m-1 , 2^n-1 ) = 2^(m,n)-1
PS: 括號"()" 都是指最大公因數的意思
2樓. 陳2009/10/06 10:47陳
恩,了解.其實此題有一些驚人的成果的,即當m為質數時2^m=2(mod m),此即費馬小定理;2^m=3(mod m)僅當m=4700063497時,且沒有比這個數還小的正整數可以滿足2^m=3(mod m),真是個誇張的數字!!-
1樓. 陳2009/10/06 08:37陳
我只能說,該引理確實起了關鍵性作用,唉,一直想不到這個技巧,難怪解不出來,欲證明該引理,可先由一個例子:求(2^32-1,2^20-1),可令d=(2^32-1,2^20-1),則d|2^32-1,d|2^20-1,二式相減得d|2^20*(2^12-1),又d為奇數,故d|2^12-1,再由d|2^20-1,二式再相減,...如此繼續,到最後由輾轉相除法原理得知必有d|2^(32,20)-1=2^4-1,故d恰等於2^4-1,觀察此例即不難証出該引理.
現在回到原題,可先假設有m|2^m-1,m為大於1之正奇數(偶數明顯不成立),則m必有一個最小的質因數p,可使p|m,因此當然有p|2^m-1,再由費馬小定理知p|2^(p-1)-1,故p|(2^m-1,2^(p-1)-1)=2^(m,p-1)-1(由該引理),而(m,p-1)必互質,即(m,p-1)=1(若不互質,則表示m還有比p小的質因數,此為矛盾),所以有p|1,得到矛盾,原命題得証.
我認為此題確實不容易,而且我被困擾了許久,現在終於解出來了,也算是放下了一塊大石,對了,那書上是怎麼証的啊?可否讓我欣賞一下??
書上的方法跟你現在寫的一樣!^^
不過他引理的部份是用證明的
先假設m>=n, m=Qn + R ,Q為商數,R為餘數
2^m-1 = 2^(Qn+R) -2^R + 2^R -1
= 2^R(2^Qn-1) + 2^R-1
又2^n-1 | 2^Qn-1
故可以知道
(2^m-1,2^n-1) = (2^n-1,2^R-1)
不斷重覆此步驟可得証引理~
都都 於 2009/10/06 08:46回覆忘了補充,引理的2可以改成任意大於1的自然數~ 都都 於 2009/10/06 08:49回覆
