[數論] 完全數 (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)」。關於梅森質數的介紹，可以參考維基百科的介紹，請點此。

[數論] 高次同餘式 (Polynomial Congruences)

參考資料
張文忠，基礎數論：原理及題解，中央圖書，2002年出版，ISBN：978-957-637-493
Polynomial Congruences 
http://www.cs.xu.edu/math/math302/04f/PolyCongruences.pdf
http://www2.latech.edu/~schroder/slides/number_theory/14_polynomial_congruences.pdf

在上一篇我們介紹並討論一次同餘式（組）的求解。本篇將討論關於高次同餘式的性質及求解方法。

一、高次同餘式介紹
一個典型的高次同餘式可表示為 $$f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots a_1x+a_0\equiv 0\; (\textrm{mod}\; m) , \textrm{where}\; a_i\in \mathbb{Z}, i=0,1,\cdots ,n$$
若模數 $m$ 是質數，我們可以透過質數的特性去探討同餘式之解的存在性及求解；若模數 $m$ 是合數，通常的處理方法是把該模數轉為質數模數加以研究。

若 $m_1, m_2,\cdots ,m_n$ 是 $n$ 個兩兩互質的正整數，$m=m_1m_2\cdots m_n$，則同餘方程式 $$f(x)\equiv 0\; (\textrm{mod}\; m)$$ 與同餘方程組  $$f(x)\equiv 0\; (\textrm{mod}\; m_i), \; i=1,2,\cdots n$$ 具有相同解。若用 $T_i$ 表示 $f(x)\equiv 0\; (\textrm{mod}\; m_i)$ 的解的個數，$T$ 表示 $f(x)\equiv 0\; (\textrm{mod}\; m)$ 的解的個數，則 $$T=T_1T_2\cdots T_n$$ 以下僅討論模數 $m$ 為質數的情況。

對於 $f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots +a_1x+a_0\equiv 0$(mod $p$)，其中 $p$ 是質數，且 $p\nmid a_i$，$i=0,1,\cdots ,n$，求解的基本方法有二：

1. 將模 $p$ 的完全剩餘系 $\left \{ 0,1,\cdots ,p-1 \right \}$ 的元素逐一代入同餘式
此方法毋需其他特殊技巧，當 $p$ 很小的時候相當實用。但當 $p$ 很大的時候，使用此方法就顯得缺乏效率。

2. 降低原式的複雜度
2.1 降低 $f(x)$ 中的 $x^i$ 的係數，或是降低 $f(x)$ 的次數。

<例1> 求解同餘式 $x^{10}+^7-x^3+3\equiv 0$ (mod $5$)
<解1> 因為 $(x,5)=1$，由 Euler's theorem 知 $x^{\phi (5)}\equiv x^4\equiv 1$ (mod $5$)。故原式可化簡為 $$x^{10}+x^7-x^3+3\equiv x^2+x^3-x^3+3\equiv x^2+3 \equiv 0\; (\textrm{mod}\; 5)$$ 即原式與 $x^2+3 \equiv 0\; (\textrm{mod}\; 5)$ 有相同的解。

將模 $5$ 的完全剩餘系 $\left \{ 0,1,2,3,4 \right \}$ 元素逐一代入 $x^2+3 \equiv 0\; (\textrm{mod}\; 5)$ ，發現此同餘式無解，故原同餘式也無解。

2.2 利用因式分解
假設 $f(x)=q(x)g(x)\equiv 0\; (\textrm{mod}\; p)$，即 $q(x)\equiv 0\; (\textrm{mod}\; p)$，$p(x)\equiv 0\; (\textrm{mod}\; p)$。

2.3 $f(x)\equiv 0\; (\textrm{mod}\; p)$ 必與一個次數小於 $p$ 的質數模 $p$ 的同餘式有相同的解
若 $f(x)$ 的次數 $n< p$，結論顯然成立。

若 $f(x)$ 的次數 $n\geq p$，由多項式的帶餘式除法知，存在兩個整係數多項式 $q(x)$ 與 $r(x)$，使 $$f(x)=(x^p-x)\cdot q(x)+r(x)$$ 其中 $r(x)$ 的次數小於 $p$。

為何選擇 $x^p-x$ 作為除式？由費馬小定理，易知 $x^p-x$ 可以被 $p$ 整除，所以 $$f(x)=(x^p-x)\cdot q(x)+r(x)\equiv r(x)\; (\textrm{mod}\; p)$$ 也就是說，$f(x)\equiv 0\; (\textrm{mod}\; p)$ 與 $r(x)\equiv 0\; (\textrm{mod}\; p)$ 同解。


二、Lagrange定理
定義：設 $p$ 是質數，且 $p\nmid a_n$，則模 $p$ 的 $n$ 次同餘式 $$f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots a_1x+a_0\equiv 0\; (\textrm{mod}\; p)$$ 最多有 $n$ 個解。

<pf> 反證法。假設 $n$ 次同餘式 $$f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots a_1x+a_0\equiv 0\; (\textrm{mod}\; p)$$ 的解超過 $n$ 個。其中 $a_n\not\equiv 0\; (\textrm{mod}\; p)$，則此式至少有 $n+1$ 個不同的解，設為 $$x\equiv \alpha _i\; (\textrm{mod}\; p)\; \; i=1,2,\cdots ,n,n+1.$$ 我們可以將原式改寫為 $$f(x)\equiv a_n(x-\alpha _1)(x-\alpha _2)\cdots (x-\alpha _n)\; (\textrm{mod}\; p).$$ 因為$f(\alpha _{n+1})\equiv 0 (\textrm{mod}\; p)$，所以 $$a_n(\alpha _{n+1}-\alpha _1)(\alpha _{n+1}-\alpha _2)\cdots (\alpha _{n+1}-\alpha _n)\equiv 0\; (\textrm{mod}\; p).$$ 由於 $p$ 是質數，且 $a_n\not\equiv 0\; (\textrm{mod}\; p)$，故存在某個 $\alpha _i$，使得 $$\alpha _{n+1}-\alpha _i\equiv 0\; (\textrm{mod}\; p)$$ 即 $$\alpha _{n+1}\equiv \alpha _i\; (\textrm{mod}\; p)$$ 這與假設矛盾。所以此方程式最多只有 $n$ 個解。

Lagrange定理僅給了一個模 $p$ 的 $n$ 次同餘式解的個數上限，並不保證解的存在性。首先，我們想知道，在什麼情況下，解的個數恰好為 $n$ 個？


三、再探解的個數
性質一：設 $p$ 為質數。若 $n\leq p$，則同餘式 $$f(x)=x^n+a_{n-1}x^{n-1}+\cdots a_1x+a_0\equiv 0\; (\textrm{mod}\; p)$$ 有 $n$ 個解的充分必要條件是 $x^p-x$ 除以 $f(x)$ 的餘式的所有係數都是 $p$ 的倍數。

<pf> 我們可以將 $x^p-x$ 寫為 $$x^p-x=f(x)\cdot q(x)+r(x)$$ 其中 $q(x)$ 是一個 $p-n$ 次的多項式，餘式 $r(x)$ 的次數小於 $n$。

充分性$(\Rightarrow )$：若所給同餘式有 $n$ 個解，由上述 2.3 知，這 $n$ 個解也會是 $r(x)\equiv 0\; (\textrm{mod}\; p)$ 的解。但 $r(x)$ 的次數小於 $n$，根據 Lagrange 定理，$r(x)$ 的係數必定都是 $p$ 的倍數。

必要性$(\Leftarrow )$：若 $r(x)$ 的係數皆可被 $p$ 整除，因為 $x^p-x\equiv 0\; (\textrm{mod}\; p)$，所以有 $f(x)q(x)\equiv 0\; (\textrm{mod}\; p)$，有 $p$ 個不同的解 $$x\equiv 0,1,\cdots ,p-1\; (\textrm{mod}\; p)$$ 若 $f(x)\equiv 0\; (\textrm{mod}\; p)$ 的解的個數 $k<n$，因為 $q(x)$ 是一個 $p-n$ 次的多項式，由 Lagrange 定理知，$q(x)\equiv 0\; (\textrm{mod}\; p)$ 的解的個數 $h\leq p-n$。因此 $f(x)q(x)\equiv 0\; (\textrm{mod}\; p)$ 的解的個數等於 $k+h<n+(p-n)=p$，但前面又說明此同餘式有 $p$ 個不同的解，故所給同餘式有 $n$ 個解。


性質二：設 $p$ 為質數，$d\mid p$，則同餘式 $x^d\equiv 1\; (\textrm{mod}\; p)$ 恰有 $d$ 個解。