2樓. 陳

2009/09/17 21:40

陳
糟糕!我一個地方寫錯了,(2^k)^h=2^k(mod h)才對,因此尚無法說明其為矛盾,我今天下午的時候發現了這個錯誤,唉,又回到原起點了,這就是此題我一直無法突破的原因啊!!

1樓. 陳

2009/09/17 10:25

陳

我終於不再被此題困擾了,想不到一個簡單的trick我竟然沒想到,真是令人汗顏!此題欲証m不整除2^m-1,m為偶數時為trivial,僅需考慮m為奇數,若m為奇質數p,則由費馬小定理知2^p=2(mod p),所以原敘述當然成立;接著考慮m是奇合成數,假設有m使得2^m=1(mod m),而m為奇合成數,則m必有奇質因數h,可使m=h*k,代回得2^(h*k)=1(mod m),因此有2^(h*k)=1(mod h),故(2^k)^h=1(mod h),由費馬小定理得知(2^k)^h=2(mod h),是為矛盾,故原式得証.

我用到一個引理:若a=b(mod n),且c為n之因數,則必有a=b(mod c),這個引理我當初一直沒想到,僅是一個簡單的trick,害我還用群跟完全剩餘系解這一題,果然是想太多@#$%