[數論] 完全數 (Perfect Number)

參考資料
傅鍾鵬，數學英雄 歐拉，凡異，2005出版，ISBN：9576945682
完全數的小故事 http://euler.tn.edu.tw/allno.htm
張鎮華，完全數與莫仙尼質數 http://episte.math.ntu.edu.tw/articles/sm/sm_02_03_1/

一、何謂完全數
定義：完全數(Perfect Number)等於除了本身以外的所有正因數的和。

我們用數學符號 $\sigma (n)$ 表示 $n$ 的正因數的和。例如 $\sigma (8)=1+2+4+8=15$。因此上述的定義可寫為 $$\textrm{n is a perfect fumber if}\; \sigma (n)=2n.$$
完全數這個名詞很早就為人所熟悉。古人認為「$6$」是屬於美神維納斯的專利，它象徵著美滿的婚姻；也有人認為是因為上帝創造世界也是花了 $6$ 天的時間；$28$ 也是一個完全數，它象徵月亮繞行地球的間：恰為 $28$ 天。

公元前 $300$ 年左右，希臘數學家歐基里德(Euclid)提出「完全數」的概念。在《幾何原本》第九卷第 $36$ 個命題(可點此查看詳細內容)首次提及完全數。歐基里德發現了第一個到第四個完全數，並給出一個完全數的定理：

令整數 $n>1$。若 $2^n-1$ 是質數，則 $2^{n-1}(2^n-1)$ 是完全數。

由於根據上述定理得到得完全數皆為偶數，這些完全數我們稱作「偶完全數」。到了18世紀，歐拉(Euler)證明了逆命題亦為真。下面我們將證明該定理之充分性及必要性。

二、證明
◎充分性$(\Rightarrow )$(Euclid)：設 $2^n-1=p$ 為質數。改寫 $2^{n-1}(2^n-1)=2^{n-1}p$ $$\begin{array} \sigma \sigma \left ( 2^{n-1}p \right ) &= \left ( 1+2+2^2+\cdots +2^{n-1} \right )+\left ( p+2p+2^2p+\cdots +2^{n-1}p \right ) \\ &= \left ( \frac{2^n-1}{2-1} \right )+p\left ( \frac{2^n-1}{2-1} \right ) \\ &= \left ( p-1 \right )\left ( 2^n-1 \right ) \\ &= 2^n\left ( 2^n-1 \right ) \\ &= 2\left [ 2^{n-1}\left ( 2^n-1 \right ) \right ]\; \; \textrm{Q.E.D.} \end{array}$$
◎必要性$(\Leftarrow )$(Euler)：see here.

求偶完全數的問題，等同於尋找適當的質數 $n$，使得 $(2^n-1)$ 為質數的問題。數學上，稱形如 $2^n-1$ 的質數為「梅森質數(Mersenne Number)」。關於梅森質數的介紹，可以參考維基百科的介紹，請點此。