關於梅森數和費馬數的兩個證明(10點)

Question

(一)n是正整數，若2^n-1是質數，則n也是質數。但逆定理「若n是質數，則2^n-1是質數」不成立，請找出最小的反例。

(二)n是正整數，若2^n+1是質數，則n必可以表為2的乘冪的形式，也就是n可以表為2^m，其中m是非負整數。

(拜託高手先不要出手，理由下文說明)
雖說江湖一點訣，說破不值三兩錢，不過難就難在說破的過程，這兩個證明當初就分別花了我一個下午才想出來，Newton說："我就像是個在海邊撿貝殼的小男孩，偶然撿到一個美麗貝殼，就足以興奮很久"，那兩個下午，我終於知道Newton撿貝殼的心情了，所以我希望以前證過的朋友先不要出手，把機會留給沒證過的人，因為我希望別人也能體會這種美妙的感覺。謝謝！千里不留名兄，要試嗎？

另外，我想這兩個證明必然在很久很久以前就已經被完成了，不然人類分解梅森數和費馬數的歷史就不會是諸位所看到的那樣了。
(這題我會公正地自選解答，所以搶第一沒用)

千里不留名兄：
你若是要證，我就給你一點提示，以下我說的就是我當初的思路：
(1)有時候我們要證"若P則Q"，發現很難證，我們可以改證"若不Q則不P"，就邏輯而言，這是相同的證明。(極重要)
(2)就第(一)題而言，我們知道n是偶數時，根據平方差公式，2^(2k)-1=(2^k-1)(2^k+1)，因此2^n-1可以分解成兩數相乘；當n是3的倍數時，根據立方差公式，2^n-1也可以分解成兩數相乘，那麼，2^(5k)-1可以分解嗎？2^(7k)-1可以分解嗎？

(3)第(二)題，「找規律」，你把n=1,2,3......16分別代入2^n+1中，然後因數分解這16個數，看看它們的因數有什麼規律，並證明這個規律，先告訴你了，n小於等於16時，只要2^n+1是合數，則它會有小於30的質因數，所以要因數分解它們應該是不太難的。
希望你找到你的貝殼。

Answer 1

不懂..............

2005-06-04 08:34:47 補充：
說真的,證明題是我的弱點,不過你的提示太明顯了,第一題我知道了,但是第二題我找得出規律,但是不會證明,就是當不為2^m的形式時,必定會有f(2^m)的因數...........

2005-06-04 18:45:00 補充：
一切都豁然開朗了..........

2005-06-04 21:36:48 補充：
(一)n是正整數，若2^n-1是質數，則n也是質數。但逆定理「若n是質數，則2^n-1是質數」不成立，請找出最小的反例。(1)當n不為質數時,n可表示為2k,3k,5k.......,其中k為大於1的整數,則2n-1必定為(2k-1)的倍數,故不為質數,因此,當2n-1為質數時,n必為質數...(2)最小的反例為n=11時,2n-1=2047=23*89(二)n是正整數，若2^n+1是質數，則n必可以表為2的乘冪的形式，也就是n可以表為2^m，其中m是非負整數。(1)n為奇數時,n可表示為(2k+1),其中k為非負整數,則2n+1=22k+1+1,因此2n+1必為21+1=3的倍數.=>不為質數....(2)n為偶數時,且n不為2m形式時,則n可表示為(2m)*k,其中k為大於1的整數,且(2,k)=1,故k為奇數,因此2n+1=2^[(2m)*k]+1必為(2^2m)+1的倍數,=>不為質數.........由(1),(2)可知,當n不為2m的形式時,2n+1不為質數,因此當2n+1為質數時,n必可表示為2m...............ps:是這樣吧!希望不會讓你失望....................

2005-06-05 08:35:42 補充：
Copestone兄:
不要給我難堪啊!我打那麼多,你才打幾個字而已耶!看來我們的程度真的差太多了...........

2005-06-05 22:46:22 補充：
1.抱歉,我承認我懶,因為我不太會打數學符號,所以能省則省,我是用"因式分解"的方式求得的.次方項為奇數次項時,必定可以分解.
2.我只是想讓你知道,你所提供的我已經吸收了,這樣就夠了啊!不是嗎?
3.還是非常感謝你的教導.........

Answer 2

算術基本定理的強大應用：在這兒，我好像沒見過數論題目，不用因子分解的。

2005-06-03 14:01:32 補充：
那通常因為用了分析的估計方法，如你只能知道某一因子在某些值之間，那時不就變成有可能知道是合數，卻找不出因子麼？你是想像得到的，你只是沒留意去想罷了。

2005-06-05 02:06:03 補充：
如果 q 是奇數，則 2^{pq} + 1 永遠可以分解成 (2^p + 1)[2^{p(q-1)} - 2^{p(q-2)} + ... -2^p + 1]
所以 2^n + 1 為質數時，則 n 沒有奇數的質因子。證畢。

2005-06-06 14:20:42 補充：
有空大家想想我的問題吧，只要是高中程度的，沒有一題是真正難的，挑戰你的是想法、創意。我本身是一個不重計算的人，我認為把公式放在本子裡，我看著就會算了，何必背起來？台灣人的數學，最缺乏的就是創意，而非解題的計算能力。

Answer 3

可是還是有人差點想不出來，就是我，費馬數那個又比梅森數那個難很多。因為不能表為2的乘冪的整數都能表為一種特別的形式，想了一個下午才領悟出來那種形式。
還有，dd，這裡你要不要回去看一下？
http://tw.knowledge.yahoo.com/question/?qid=1105053106824

2005-06-03 11:56:13 補充：
大概是我的功力太淺了，我無法想像不找出某數的因數卻能證明它是合數，是什麼情形。但我知道有人作得到。
會不會用到算數基本定理我不知道，我的方法是分別證明兩個同餘式，對於第一次證的人而言，證明這兩個同餘式是不難的，難在把它們找出來吧！

2005-06-05 20:51:16 補充：
千里不留名兄：
為什麼第(一)題中，2^n-1必定為(2^k-1)的倍數呢？你可以用同餘式，也可以像Copestone一樣用因式分解，總之我覺得這部份是需要證明的。
另外，只要n是k的倍數，2^n-1就必定是(2^k-1)的倍數，n不一定要是k的質數倍喔！
第(二)題也是喔！為什麼2^[(2^m)*k]+1必為[2^(2^m)]+1的倍數呢？
不過我想Copestone已經告訴你為什麼了。另外，當n不為2的乘冪時，不用寫得那麼麻煩，你可以說n=pq，其中p為正整數，q為≧3的奇數。

2005-06-07 20:09:54 補充：
明明可以用同餘的呀！
第一題
n=1時命題為真。
當n≧2時，若n不為質數,必為合數，可寫成n=pq,p≠1，p≠n
2^p≡1(mod 2^p-1)(自己是自己的倍數)
2^pq≡1^q(mod 2^p-1)
2^n≡1(mod 2^p-1)
2^p-1≠1，2^p-1≠2^n-1，故2^p-1為2^n-1的真因數，2^n-1為合數。

2005-06-07 20:11:49 補充：
第二題
若n不為2的乘冪，必可寫為n=pq，q為3以上的奇數
2^p≡(-1)(mod 2^p+1)
2^pq≡(-1)^q(mod 2^p+1)
2^n≡(-1)(mod 2^p+1)
2^p+1≠1，2^p+1≠2^n+1，故2^p+1為2^n+1的真因數，2^n+1為合數。

Answer 4

這二個在數論的領域都算是很基本的東西

2005-06-02 13:16:36 補充：
只是多了一個步驟
不過聰明的你還是證明出來了呀

2005-06-07 09:02:59 補充：
若n為合數,可寫成n=pq,p>1,q>1
則2^pq-1=(2^p-1)(2^p(q-1)+2^p(q-2)+...+2^p+1)
為合數
所以矛盾

2005-06-07 09:06:40 補充：
第二題
若n有奇質因數,可以寫成n=p(2k+1),k>0
則2^p(2k+1)+1=(2^p+1)(2^p(2k)-2^p(2k-1)+...-2^p+1)
為合數
所以矛盾,所以n沒有奇質因數
所以n=2^m

2005-06-07 09:07:52 補充：
原本想說要回答的~沒想到已經結束了@@