數學傳播

例題05: 試分解 $F_5, F_6, F_7$ 三個費馬數。

解: 執行 FactorInteger 指令如下：

In[5]:=Table[F[n], {n, 5, 7}] // FactorInteger
Out[5]={{{641,1},{6700417,1}},
        {{274177,1},{67280421310721,1}},
        {{59649589127497217,1},
         {5704689200685129054721,1}}}

所以得到此三個費馬數的分解式如下： \begin{eqnarray*} F_5 &=& 641\times 6700417 \\ F_6 &=& 274177\times 67280421310721 \\ F_7 &=& 59649589127497217\times 5704689200685129054721 \end{eqnarray*}

例題06: 試計算 $\gcd(123456789, 987654321)$。

解: 我們用上面的指令得到 $\gcd(123456789, 987654321)=9$。

In[6]:= GCD[123456789,987654321]
Out[6]= 9

3.二進GCD演算法： 假設 $1\lt a\lt b$ 為二正整數。記得嗎？在上面的輾轉相除法中， 我們所用到的基本原理是： $$\gcd(a,b)=\gcd(a,b-ma) ,$$

其中所取的 $m$ 乃最大的正整數使得 $b-ma\ge 0$。此 $m$ 是透過長除法完成的，但長除法之運算相對地說來是挺花時間的。 若取 $m=1$, 則速度當然會很快。 另外除以 2 之運算也是極端快速的，特別是在機器語言中。若 $a$ 與 $b$ 都是偶數，則我們有 $$\gcd(a,b)=2\times\gcd(a/2,b/2)\hbox{。}$$

若 $a$ 為奇數， $b$ 為偶數，則我們有 $$\gcd(a,b)=\gcd(a,b/2)\hbox{。}$$

所以得到這個二進GCD演算法的步驟如下：

1. 若 $a$ 與 $b$ 都是偶數，則將二數同時除以 2 ； 亦即將 $a$ 與 $b$ 分別用 $a/2$ 與 $b/2$ 來取代。 重複此步驟直到有奇數出現為止。令 $r$ 為執行此步驟的次數。
2. 若有偶數，將此偶數擺在 $b$ 的位置並將 $b$ 用 $b/2$ 來取代。重複此步驟直到變成奇數為止。
3. 若 $b=1$, 則 $\gcd(a,b)=2^{\,r}$。
4. 若都是大1的相異奇數，則將大數擺在 $b$ 的位置並將 $b$ 取代為 $b-a$ 並回到步驟(b)。
5. 若 $b=a$, 則 $\gcd(a,b)=2^{\,r}\times a$。

為方便起見，我們用 $(a,b)$ 來表示 $\gcd(a,b)$。且看下面的例子：

1. $(30,42)=2(15,21)=2(15,6)=2(15,3)=2(3,15) =2(3,12)=2(3,6)\\ =2(3,3)=6$。
2. $(56,72)=2(28,36)=2^2(14,18)=2^3(7,9)=2^3(7,2)=2^3(7,1) =2^3$。
3. $(77,133)=(77,56)=(77,28)=(77,14)=(77,7)=(7,77)=(7,70)\\ =(7,35)=(7,28)=(7,14)=(7,7)=7$。

在上面輾轉相除法中，我們並沒有去驚動到商 $q_1,q_2,q_3,\ldots$, 甚至連碰都沒碰一下。感覺上，他們應該很有用才對， 且看下面的分析。通常談到最大公因數時， 我們都會提到一個非常基本的事實：給予二整數 $a$ 與 $b$, 必存在有整數 $x$ 與 $y$ 使得 $$ax+by=\gcd(a,b)\hbox{。}$$ 換句話說， $a$ 與 $b$ 的最大公因數可以用這兩個數的一個線性組合來表示。 在理論上，這個事實有著很重要的應用，特別是當 $a$ 與 $b$ 互質時。但怎麼證明呢？可簡單描述如下：考慮形如 $ax+by$ 之整數所成的集合。透過正整數之良序性， 我們知道這個集合有一最小的正整數，姑且稱之為 $d$。 然後再利用長除法可證明這個集合中的每一個元素都是 $d$ 的一個倍數。由此很容易就可推論得到我們所要的結果 (試將完整的證明寫下來)。 這樣的證明，雖說是簡潔漂亮；但美中不足的是， 在整個證明的過程當中，我們尋不到怎麼樣去找 $x$ 與 $y$ 的蛛絲馬跡。我們要的乃是一個建構式的證明 (constructive proof), 亦即在證明當中，同時也能告訴我們怎麼樣去找 $x$ 與 $y$。 在目前的例子中，其演算法實際上是隱藏於輾轉相除法中。

所以讓我們重頭再來一遍：令 $a=r_0,\quad b=r_{-1}$ 。輾轉相除之，得到 \begin{equation} r_{j-2}=q_jr_{j-1}+r_j,\quad j=1,2,\ldots,n+1\hbox{。} \label{1} \end{equation} 這意味著 $r_{n+1}=0$ 且 $r_n=\gcd(a,b)$。若從第 $n$ 個除式開始逆推回去， 不難看出最後的餘數可用前面兩個餘數的一個線性組合來表示； 如此這般一直往前推，到末了就得到我們所要的結果 (試著將完整的證明寫下來)。然而不同的是，這一次我們實實在在的算出了 $x$ 與 $y$。

再看一次上面的例題03： $\gcd(482,1180)=2$, 我們會用到那兒計算時的一些數。透過其中的那些餘數 $216,50,16,2$ 逆流而回到原先的兩個數 $1180$ 與 $482$, 而最後得到最大公因數 2 為 $1180$ 與 $482$ 的一個組合。由第四行開始，我們有 $$2=50-3\cdot 16,$$ 所以我們可以把 2 表示成前兩個餘數的組合。往上移動一行， 我們可將餘數 16 寫成 216 與 50 的組合，然後代入上式得 $$16=216-4\cdot 50 \Longrightarrow 2=50-3\cdot 16=50-3\cdot (216-4\cdot 50)=13\cdot 50-3\cdot 216\hbox{。}$$ 現在我們已經用過 gcd 演算過程中後面兩個非零餘數。將上一個未用到過的餘數 50 表示成 482 與 216 的組合，然後代入上式得 $$2=13\cdot (482-2\cdot 216) -3\cdot 216=13\cdot 482-29\cdot 216\hbox{。}$$ 最後將 216 代換成 $1180-2\cdot 482$ 得到 $$2=13\cdot 482-29\cdot(1180-2\cdot 482)= 71\cdot 482-29\cdot 1180\hbox{。}$$ 此即最大公因數 2 表示成 1180 與 482 之組合的式子。只要輾轉相除時的計算式不太多的話， 那麼即使是用手算也不是太費工夫。 但一般而言，此法不太適用於搭配電腦來使用。 算的時候似乎有點費工夫，因為沒有遞迴法則可言。

怎麼樣才能找到那一個更美、更好且更適合電腦來使用的方法呢？ 我們知道每一個 $r$ 都是前兩個 $r$ 的組合，因此可得到如同 $r_n$ 一樣的結論；也就是說我們有 $$\hbox{每一個 }r\hbox{ 都是 }a\hbox{ 與 }b \hbox{ 的線性組合。}$$ 這句話孕育著呼之欲出的 $x$ 與 $y$ 之遞迴公式。怎麼說呢？且看：令 \begin{equation} r_{j}=x_ja+y_jb,\quad j=1, 2,\ldots,n\hbox{。}\label{2} \end{equation}

比較(\ref{1})式及(\ref{2})式，得到 $j=1$ 時我們有 $$x_1a+y_1b=r_1=-q_1a+b\Rightarrow x_1=-q_1,\quad y_1=1\hbox{。}$$ 而 $j=2$ 時，我們卻有 $$x_2a+y_2b=r_2=-q_2(x_1a+y_1b)+a\Rightarrow x_2=-q_2x_1+1,\quad y_2=-q_2y_1\hbox{。}$$ 當 $j\ge 3$ 時我們終於有 \begin{eqnarray*} x_ja+y_jb=r_j&=&-q_j(x_{j-1}a+y_{j-1}b)+ (x_{j-2}a+y_{j-2}b)\\ &=& (-q_jx_{j-1}+x_{j-2})a+(-q_jy_{j-1}+y_{j-2})b, \end{eqnarray*} 因而得到 $j=3,4,\ldots,n$ 時的遞迴公式就是： $$x_j=-q_jx_{j-1}+x_{j-2},\qquad y_j=-q_jy_{j-1}+y_{j-2}\hbox{。} $$ 雖然這遞迴公式在 $j=1,2$ 時沒有意義，但很容易可以看出只要我們定義 $$x_{-1}=0,\ \ x_0=1,\ \ y_{-1}=1,\ \ y_0=0,$$ 則所有的問題就煙消雲散。因而此二數列 $\{x_j\}$ 與 $\{y_j\}$ 可定義如下： \begin{eqnarray} x_{-1}=0, &x_0=1, &x_j=-q_jx_{j-1}+x_{j-2}, j=3,4,\ldots,n\hbox{；} \label{3}\\ y_{-1}=1, &y_0=0, &y_j=-q_jy_{j-1}+y_{j-2}, j=3,4,\ldots,n\hbox{。} \label{4} \end{eqnarray} 由(\ref{3})及(\ref{4})式，很快就可以算出 $x_n$ 與 $y_n$ 因此得到 $a$ 與 $b$ 的最大公因數為 \begin{equation} \gcd(a,b)=x_na+y_nb\hbox{。}\label{5} \end{equation} 我們再一次看上面的例題03： $\gcd(482,1180)=2$, 這次用到公式(\ref{5})。在例題03當中，其商依序為 $q_1=2$, $q_2=2$, $q_3=4$, $q_4=3$, $q_5=8$ 。我們可以很快算出 $x_j$ 及 $y_j$ 如下：

所以我們得到 $$\gcd(a,b)=71\cdot 482-29\cdot 1180\hbox{。}$$

注意: 上述的方法通常稱之為延伸 (extended) 輾轉相除法，在下面解某些同餘式時會用到。

在數學運算大師 MATHEMATICA 中與此有關的指令如下：

• ExtendedGCD[$a,\,b$] 算出 $\gcd(a,b)$ 且將其表成 $a$ 與 $b$ 的組合。

例題07: 試求 $\gcd(482,1180)$ 並表示成此二數的一個線性組合。

解: 我們用上面的指令得到 $\gcd(482,1180)=2$ 且 $$2=71\cdot 482-29\cdot 1180\hbox{。}$$

In[7]:= ExtendedGCD[482, 1180]
Out[7]= {2,{71,-29}}

例題08: 試求方程式 $123456789x+987654321y=9$ 的整數解。

解: 我們用上面的指令得到 $x=-8$ 與 $y=1$。

In[8]:= ExtendedGCD[123456789, 987654321]
Out[8]= {9,{-8,1}}

在數論當中， 最基本又最有用的觀念之一就是模算術或同餘的觀念。 我們就從孫子算經^{8 8} 約成書於第四世紀， 作者生平和編寫年代都不清楚。現今傳本共有三卷。 卷上敘述記數的縱橫相間制度和乘除法則， 卷中舉例說明分數算法和開平方法。卷下第 31 題，可以看作後世雞兔同籠題的始祖，後來傳到日本， 變成鶴龜算。請參考下面網頁 http://www.edp.ust.hk/math/history/6/ 說起。首先「三三數之剩二」是什麼意思呢？ 那不過說某一個數 $x$ 被 3 除剩餘 2; 換句話說， $x-2$ 被 3 整除。我們用下式表示「三三數之剩二」

$$x\equiv 2\pmod{3}\hbox{。}$$ 一般而言，令 $n$ 為一正整數。對任意二整數 $a$ 與 $b$, 若 $n\mid a-b$ 則我們稱之為在模 $n$ 之下， $a$ 同餘 $b$, 用符號 $$a\equiv b\pmod{n}$$ 表示之。反之， $a\not\equiv b\pmod{n}$ 表示 $a,b$ 在模 $n$ 之下不同餘。例如： $52\equiv 27\!\!\!\!\pmod{5}$, $-19\equiv 37\!\!\!\!\pmod{7}$, $11\not\equiv 91\!\!\!\!\pmod{13}$。在理論性的論證當中， $a\equiv b\pmod{n}$ 通常改寫為 $b=a+nk$ ($k$ 為一整數) 較為方便。你可以將同餘式看成好像是等式一樣， 在式子的兩邊執行你所要的四則運算 (試證明之！) ，唯一需要小心的當然是除的時候。且看下面幾個例子， 即可明白是怎麼一回事。

例題09: 試求同餘方程式 $x+11\equiv 7\pmod{17}$ 的解。

解: $x\equiv 7-11\equiv -4\equiv 13\pmod{17}$ 。答案若寫成負的並沒什麼錯誤。但當我們在模 $n$ 之下工作時，通常將最後的答案表示為介於 $0$ 與 $n-1$ 之間的整數。

除法原理: 在模 $n$ 下，只要除數與 $n$ 互質，你就可以將兩數相除。

例題10: 試求同餘方程式 $4x+11\equiv 7\pmod{17}$ 的解。

解: $4x\equiv 7-11\equiv -4\pmod{17}$, 所以 $x\equiv -1\equiv 16\pmod{17}$。被 4 除沒問題，因為 $\gcd(4,17)=1$。

例題11: 試求同餘方程式 $5x+7\equiv 11\pmod{17}$ 的解。

解: $5x\equiv 4\pmod{17}$。現在怎麼辦呢？ 兩邊同時除以 5 就好了嗎，但 $4/5$ 在模 17 之下是什麼意思呢？我們知道 $4\equiv 21\equiv 38\equiv 55\equiv\cdots\pmod{17}$, 所以 $5x\equiv 4\pmod{17}$ 與 $5x\equiv 55\pmod{17}$ 是一樣的。現在我們可除以 5 得到 $x\equiv 11\pmod{17}$ 為其答案。注意 $4\equiv 11\cdot 5 \pmod{17}$, 所以在模 17 之下 11 就如同是 $4/5$ 一樣。

另解: 我們也可從另一角度來解此同餘方程式。因為 $5\cdot 7\equiv 1\!\!\!\!\pmod{17}$, 我們看出在模 17 之下 7 是 5 的乘法反元素。因此，除以 5 可由乘以 7 來完成，如下： $5x\equiv 4\pmod{17}\Longrightarrow x\equiv 35x\equiv 28 \equiv 11\pmod{17}$。

除法原理證明: 從上一節我們知道，若 $\gcd(a,n)=1$ 則存在有整數 $x$ 與 $y$ 使得 $ax+ny=1$, 亦即 $ax\equiv 1\pmod{n}$。因此在模 $n$ 之下， $x$ 是 $a$ 的乘法反元素，故得證。

注意: 用上一節的延伸輾轉相除法即(\ref{3})式來計算 $x$ 是相當省時的。$y$ 則不需要算，因為在模 $n$ 之下，不管是多少都會被磨掉。

例題12: 試求同餘方程式 $1111111x\equiv 4 \pmod{1234567}$ 的解。

解: 從例題04得到 $q_1\!=\!1$, $q_2\!=\!9$, $q_3\!=\!17636$, $q_4\!=\!1$, $q_5\!=\!1$, $q_6\!=\!31$。因此可得 $x_{-1}\!=\!0$, $x_0\!=\!1$, $x_1\!=\!-1$, $x_2\!=\!10$, $x_3\!=\!-176361$, $x_4\!=\!176371$, $x_5\!=\!-352732$, 這告訴我們 $1111111\cdot (-352732)+1234567\cdot y_5=1$, 由此得知 $1111111\cdot (-352732)\equiv 1\pmod{1234567}\hbox{。}$ 將原先的同餘式兩邊同時乘上 $-352732$ 得到 $x\equiv -1410928\equiv 1058206\pmod{1234567}\hbox{。}$ 在實作上，這意味著如果我們在模 1234567 之下工作而且碰到分數 $4/1111111$, 那麼就以 1058206 取代之。這似乎是有點奇怪， 但不妨想一想 $4/1111111$ 指的是什麼呢？ 這只不過是一個符號代表乘以 1111111 之後會得到 4 的那個數。當我們在模 1234567 之下時， 1058206 也具有這個性質，因 $1111111\times 1058206\equiv 4\pmod{1234567}\hbox{。}$

在數學運算大師 MATHEMATICA 中與此有關的指令如下：

• Mod[$k,\,n$] 將 $k$ 被 $n$ 除所得的餘數，亦即 $k\pmod{n}$。

例題13: 試計算 $123\cdot 456\pmod{789}$。

解: 使用上面的指令，得到答案為 $69\pmod{789}$。

In[9]:= Mod[123*456,789]
Out[9]= 69

總結上述討論過的一些東西，摘要如下：

• 在模 $n$ 之下求乘法反元素 $a^{-1}\pmod{n}$
  1. 使用延伸輾轉相除法^{9 9} 僅求 $s$ 即可，不需要算 $t$, 理由已經在上面的注意提過。，求出整數 $s$ 與 $t$ 使得 $as+nt=1$。

  2. $a^{-1}\equiv s\pmod{n}$。
• 當 $\gcd(a,n)=1$ 時，解同餘方程式 $ax\equiv c\pmod{n}$ ($\Leftrightarrow$ 當 $\gcd(a,n)=1$ 時，在模 $n$ 之下，計算分數 $c/a$ 之值)
  1. 使用延伸輾轉相除法^{10 10} 同上。 ，求出整數 $s$ 與 $t$ 使得 $as+nt=1$。

  2. 答案為 $x\equiv cs\pmod{n}$($\Leftrightarrow$ 將分數 $c/a$ 取代為 $cs\pmod{n}$)。
• 當 $\gcd(a,n)=d>1$ 時，解同餘方程式 $ax\equiv b\pmod{n}$
  1. 若 $d\not\, b$, 則此同餘方程式無解。
  2. 若 $d\,\, b$。考慮新的同餘方程式 $$\frac{a}{d}\,x\equiv\frac{b}{d}\pmod{\frac{n}{d}} \hbox{。}$$ 因 $\frac{a}{d},\,\frac{b}{d},\,\frac{n}{d}$ 都是整數且 $\gcd(\frac{a}{d}, \,\frac{n}{d})=1$。按上述步驟得一解 $x_0$。
  3. 原同餘方程式 $ax\equiv b\pmod{n}$ 之解為 $$x_0,\ x_0+\frac{n}{d},\ x_0+2\,\frac{n}{d},\ldots,\ x_0+(d-1)\frac{n}{d}\pmod{n}\hbox{。}$$

例題14: 試求同餘方程式 $12x\equiv 21\pmod{39}$ 的解。

解: 因為 $\gcd(12,39)=3$, 此最大公因數可以整除 21 。除以 3 得到一新的同餘方程式 $4x\equiv 7\pmod{13}$ 。試幾個值，或透過延伸輾轉相除法可得一解 $x_0=5$ 。所以原同餘方程式 $12x\equiv 21\pmod{39}$ 之解為 $$x\equiv 5,\,18,\,31\pmod{39}\hbox{。}$$

在序曲 [19] 中， 我們知道解密的過程裡需要執行如 $848^{187}\pmod{1189}$ 之計算。如果我們先算出848的187次方，然後簡化至模1189之下； 那麼我們就得跟非常大的數打交道。將848自乘187次， 這是一個很大的數。表面上你得執行186次的乘法，這相當花時間。 所以在那邊，我們提出了連續平方法來解決 $848^{187}\pmod{1189}$ 的計算問題。如此一來， 原先需執行186次乘法的工作，現在只要12次就了結； 而且在整個計算過程當中絕對不會碰到一個比 $1189^2$ 還大的數。

輕而易舉的，我們可將此一算法推廣用來計算 $a^b\pmod{n}$, 其中執行模 $n$ 下的乘法次數頂多是 $2\log_2(b)$, 而在整個計算過程當中絕對不會碰到一個比 $n^2$ 還大的數。 這意味著次冪的運算可很快完成，而且不需要用到太多的記憶體。

當 $a, b, n$ 都是 100 位數時這個方法是非常有用的。如果我們算出 $a^b$, 然後簡化至模 $n$ 之下，那麼電腦的記憶體就有可能會溢位(overflow)：想想看 $a^b$ 有多大呢？其位數超過 $10^{100}$, 而此數又比宇宙中所有粒子的總數還要多。然而，計算 $a^b\pmod{n}$ 依目前的演算法來估計不會超過 700 個步驟即可完成，而且在整個計算過程當中絕對不會碰到一個超過 200 位的數。

令 $b_1b_2b_3\cdots b_w$ 為整數次冪 $b$ 的二進位表示法 (如 $b=1011$ 表示 $b_1=1,b_2=0,b_3=1,b_4=1$)。 上述之演算法步驟如下： (注意 $r_w\equiv a^b\pmod{n}$)

1. 從 $k=1$ 開始，且令 $s_1=1$。
2. 若 $b_k=1$, 令 $r_k\equiv s_k a\!\pmod{n}$; 否則令 $r_k=s_k\!\pmod{n}$。
3. 令 $s_{k+1}\equiv r_k^2\pmod{n}$。
4. 若 $k=w$, 停止；若 $k\lt w$, 則將 $k$ 增加 1 並回到步驟 2。

在數學運算大師 MATHEMATICA 中與此有關的指令如下：

• PowerMod[$a,\,b,\,n$] 將 $a^b$ 被 $n$ 除所得的餘數，亦即 $a^b\pmod{n}$。
• PolynomialMod[$p,\,n$] 將多項式 $p$ 的係數化簡至 $\pmod{n}$ 下。

例題15: 試計算 $234567^{\, 876543} \pmod{565656565}$。

解: 使用上面的指令，得到答案為 $473011223\pmod{565656565}$。

In[10]:= PowerMod[234567,876543,565656565]
Out[10]= 473011223

例題16: 試計算 $87878787$ 在模 $9191919191$ 之下的乘法反元素。

解: 取 $-1$ 次方即乘法反元素，故得 $7079995354\!\!\!\pmod{9191919191}$。

In[11]:= PowerMod[87878787,-1,9191919191]
Out[11]= 7079995354

例題17: 試求同餘方程式 $7654x\equiv 2389 \pmod{65537}$ 的解。

解: 兩種解法如下：

In[12]:= Solve[{7654*x==2389,Modulus==65537},x,Mode->Modular]
Out[12]= {{Modulus->65537,x->43626}}
In[13]:= Mod[PowerMod[7654,-1,65537]*2389,65537]
Out[13]= 43626

現在回到孫子算經中「問物幾何？」的問題。 「物不知其數，三三數之剩二，五五數之剩三，七七數之剩二」 可用同餘式表示如下： $$\cases{ x \equiv 2 &$\pmod{3} $\cr x \equiv 3 &$\pmod{5}$\cr x \equiv 2 &$\pmod{7}$}$$ 「韓信點兵問題」就是求一組同餘式的公解。孫子算經不僅僅是提供了答案並給出了解決的方法。德國數學家高斯於 1801 年出版算術探究中明確寫出下述定理。 1852 年英國基督教士 Alexander Wylie (1815-1887) 將孫子算經對此一問題的解法傳到歐洲，1874 年 L. Mathiesen 指出來孫子算經之解法符合高斯的定理， 從而在西方的數學史裏將這一個定理稱為中國剩餘定理 (Chinese remainder theorem)。 我們先敘述最簡單的版本，然後再作一般的推廣。

孫子定理: 若 $m, n$ 為互質的兩個正整數，則對任意給予的正整數 $a, b$ 必存在唯一的正整數 $x\pmod{mn}$ 滿足聯立同餘方程組： $$\cases{ x \equiv a &$\pmod{m} $\cr x \equiv b &$\pmod{n}$}$$

例題18: 試求下列聯立同餘方程組的解： $$\cases{ x \equiv 3 &$\pmod{7} $\cr x \equiv 5 &$\pmod{15}$}$$

解: $x\equiv 80 \pmod{105}$ (注意： $105=7\cdot 15$)。因為 $80\equiv 3\pmod{7}$ 且 $80\equiv 5\pmod{15}$, 所以 80 是一個解。中國餘數定理保證存在有解，而且說到在模 $mn=105$ 之下，此解是唯一的。

怎麼找到這個答案的呢？

對小數 $m$ 與 $n$ 而言，方法之一是按大小列出 在模 $n$ 之下與 $b$ 同餘的數，直到你挑選到其中一個被 $m$ 除餘 $a$ 的數為止。例如，在模 $15$ 之下與 $5$ 同餘的數為 $$5,\ 20,\ 35,\ 50,\ 65,\ 80,\ 95,\ \cdots\ $$ 模 7 之後，變為 $5, 6, 0, 1, 2, 3, 4,\cdots$。因為我們要的是 $3\pmod{7}$, 所以選取 80。對大數 $m$ 與 $n$ 而言，列表比對的話有可能效率非常低。 然而，同樣的想法還是行得通的。在模 $n$ 之下與 $b$ 同餘的數為 $b+nk$ ($k$為一整數)， 所以我們必須解同餘式 $b+nk\equiv a\pmod{m}$, 亦即 $$nk\equiv a-b\pmod{m}\hbox{。}$$ 因為我們假設 $\gcd(m,n)=1$, 所以在模 $m$ 之下 $n$ 有乘法反元素 $n^{-1}\pmod{m}$。兩邊同乘此乘法反元素可得 $$k\equiv n^{-1}(a-b)\pmod{m}\hbox{。}$$ 代回 $x=b+nk$, 然後簡化至模 $mn$ 之下，即得其解。

例題19: 解下列聯立同餘方程組： $$\cases{x \equiv 7 &$\pmod{1234567}$\cr x \equiv 11 &$\pmod{1111111}$}$$

解: 首先，例題09的演算告訴我們 $$1111111^{-1}\pmod{1234567}\equiv -352732\hbox{。}$$ 因此可得 $$k\equiv 1111111^{-1}(7-11)\equiv -352732\cdot -4\equiv 176361\pmod{1234567} \hbox{。}$$ 所以其解為 $$x\equiv 11+1111111\cdot 176361\equiv 195956647082 \pmod{1371740973937}\hbox{。}$$

如何使用孫子定理？

如果你所面對的同餘方程式是在一合成數模 $n=\prod_{pn}p^a$ 之下，則解題的關鍵想法是，按 $n$ 的分解式將方程式拆開成幾個在模 $p^a$ 之下的同餘方程式。解決完這些同餘方程式後， 再透過孫子定理重組得到在模 $n$ 之下的答案。優點是化繁為簡，通常分析在質數模或質數次冪模之下的同餘式遠比直接去面對合成數模之下的同餘式容易。

假設你要解同餘方程式 $x^2\equiv 1\pmod{35}$。因為 $35=5\cdot 7$, 所以拆開而成一對同餘方程式 $$\cases{x^2\equiv 1\pmod{5}\cr x^2\equiv 1\pmod{7}}$$ 現在觀察得知 $x^2\equiv 1\pmod{5}$ 有兩個解： $x\equiv \pm 1\pmod{5}$, 而 $x^2\equiv 1\pmod{7}$ 也有兩個解：$x\equiv \pm 1\pmod{7}$ 。所以有四種不同的組合方式分別得到解如下：

\begin{eqnarray*} x\equiv\ \ 1 &\pmod{5}, &x\equiv\ \ 1 &\pmod{7} &\Longrightarrow &x\equiv\ 1 &\pmod{35},\\ x\equiv\ \ 1 &\pmod{5}, &x\equiv -1 &\pmod{7} &\Longrightarrow &x\equiv\ 6 &\pmod{35},\\ x\equiv -1 &\pmod{5}, &x\equiv\ \ 1 &\pmod{7} &\Longrightarrow &x\equiv 29 &\pmod{35},\\ x\equiv -1 &\pmod{5}, &x\equiv -1 &\pmod{7} &\Longrightarrow &x\equiv 34 &\pmod{35}. \end{eqnarray*}

所以我們得知，同餘方程式 $x^2\equiv 1\pmod{35}$ 的解為 $x\equiv 1,\ 6,\ 29,\ 34\pmod{35}$。

注意: 一般而言，若 $n=p_1p_2\cdots p_r$ 為 $r$ 個相異奇質數的乘積，則同餘方程式 $x^2\equiv 1\pmod{n}$ 有 $2^{\,r}$ 個解。此乃下述更一般形式化之孫子定理所結出來的果實。

孫子定理(一般形式): 若 $m_1, m_2, \ldots, m_k$ 為兩兩互質的 $k$ 個正整數，則對任意給予的 $k$ 個整數 $a_1, a_2, \ldots, a_k$ 必存在唯一的整數 $x\pmod{m}$, 此處 $m=m_1m_2\cdots m_k$ 滿足聯立同餘方程組： $$\cases{x\equiv a_1 &$\pmod{m_1}$ \cr x\equiv a_2 &$\pmod{m_2}$ \cr \quad\vdots &$\quad\vdots$ \cr x\equiv a_k &$\pmod{m_k}$}$$ 例如，此定理保證韓信點兵問題的聯立同餘方程組： $$\cases{ x \equiv 2 &$\pmod{3} $\cr x \equiv 3 &$\pmod{5}$\cr x \equiv 2 &$\pmod{7}$}$$ 恰有一個解 $x\pmod{105}$ 。其實，孫子給出答案為「答曰：二十三。」 事實上，這是最小的正整數解。他又說出其演算技巧為 「術曰：三三數之剩二，置一百四十；五五數之剩三，置六十三； 七七之數剩二，置三十。并之得二百三十三。以二百一十減之， 即得。凡三三數之剩一，則置七十；五五數之剩一，則置二十一； 七七數之剩一，則置十五。一百六以上，以一百五減之，即得。」 這段話寫成數學式子就是： \begin{eqnarray*} x &=& 2\times 70+3\times 21+2\times 15-2\times 105\\ &=& 140+63+30-210\\ &=& 23 \end{eqnarray*} 如何找到這個解的呢？其演算法如下 (其實這就是孫子定理的一個證明)：

1. 算出 $m=m_1m_2\cdots m_k$。
2. 對 $j=1,2,\ldots, k$, 算出 $z_j=m/m_j$。
3. 對 $i=1,2,\ldots, k$, 利用延伸輾轉相除法算出 $y_i=z_j^{-1}\pmod{m_j}$。
4. 令 $x=a_1y_1z_1+\!\cdots\!+a_ky_kz_k\!\!\pmod{m}$, 則 $x\equiv a_j\!\!\pmod{m_j}\ \forall j$。

在數學運算大師 MATHEMATICA 中與此有關的指令如下：

• ChineseRemainderTheorem[ $\{a1,...,ak\},\,\{m1,...,mk\}$] ^{11 11} 注意： 在下達這個指令之前，得先載入「Number Theory」的套裝軟體， 指令如下：$\lt \lt$ NumberTheory`NumberTheoryFunctions`

  滿足下列聯立同餘方程組的唯一解 $x\pmod{m_1m_2\cdots m_k}$ ： $$\cases{x\equiv a_1 &$\pmod{m_1}$ \cr x\equiv a_2 &$\pmod{m_2}$ \cr \quad\vdots &$\quad\vdots$ \cr x\equiv a_k &$\pmod{m_k}$}$$

例題20: 試解韓信點兵問題： $$\cases{ x \equiv 2 &$\pmod{3} $\cr x \equiv 3 &$\pmod{5}$\cr x \equiv 2 &$\pmod{7}$}$$ 解:使用上面的指令得到答案為 23。

例題21: 試解聯立同餘方程組： $$\cases{ x \equiv 2 &$\pmod{78} $\cr x \equiv 5 &$\pmod{97}$\cr x \equiv 1 &$\pmod{119}$}$$

解: 使用上面的指令得到答案為 647480。

In[14]:= ＜＜NumberTheory`NumberTheoryFunctions`
In[15]:= {ChineseRemainderTheorem[{2, 3, 2}, {3, 5, 7}],
  ChineseRemainderTheorem[{2, 5, 1}, {78, 97, 119}]}
Out[15]= {23, 647480}

驗算如下：

In[16]:= Mod[{23, 647480}, {{3, 5, 7}, {78, 97, 119}}]
Out[16]= {{2, 3, 2}, {2, 5, 1}}

在序曲中，我們用到了費馬小定理。此定理看似艱深， 其實只需用到大家耳熟能詳的數學歸納法及二項式定理， 而所得到的結果還更一般化。說明如下：令 $p$ 為一質數。 對所有的正整數 $k$, 二項式定理告訴我們 $$(k+1)^p\stackrel{?_1}{\equiv} k^p+1\pmod{p}\hbox{。}$$ 藉著數學歸納法馬上得證 $k^p\equiv k\pmod{p}$。 另一方面，若 $a$ 為一負整數則 $a=-k$, 此 $k$ 為一正整數。 所以我們有(請在下標問號處提供理由！) $$ a^p=(-k)^{\,p}\stackrel{?_2}{\equiv}-k^{\,p} \stackrel{?_3}{\equiv}-k=a\pmod{p}\hbox{。} $$ 然而， $a=0$ 此同餘式顯而易見，故得證下述之定理。

定理: 若 $p$ 為一質數，則對所有的整數 $a$ 我們恆有 $$a^{p-1}\equiv 1 \pmod{p}\hbox{。}$$

換句話說， $p\mid (a^p-a)=a(a^{p-1}-1)$。如果 $p\not\,a$, 那麼我們馬上得證($?_4$)下述之費馬小定理。

費馬小定理: 若 $p$ 為一質數且 $p\not\,a$, 則 $$a^{p-1}\equiv 1 \pmod{p}\hbox{。}$$

例如 $2^{10}= 1024 \equiv 1 \pmod{11}$。由此可算出 $2^{53}\pmod{11}$ 如下： $$2^{53}=(2^{10})^5 2^3\equiv 1^52^3\equiv 8\pmod{11} \hbox{。}$$

費馬小定理另一證明: 考慮集合 $F=\{1, 2, b, \ldots, p-1\}$ 並考慮將 $a$ 乘上 $F$ 中每一個元素之後所形成的集合 $$aF=\{a, 2a, 3a, \ldots, (p-1)a\}\hbox{。}$$ 不難看出，在模 $p$ 之下集合 $aF$ 中每一個元素會跟集合 $F$ 中的一個而且是唯一的一個元素同餘($?_5$)。所以得到 $$(p-1)!a^{p-1}=a(2a)(3a)\cdots (p-1)a\equiv (p-1)!,$$ 故得證($?_6$)。

注意: 當我們在模11之下工作時。對次冪而言， 本質上我們是在模 10 而非模 11 之下工作。換句話說，從 $53\equiv 3\pmod{10}$ 我們可推論而得到 $2^{53}\equiv 2^3\pmod{11}$。

費馬小定理逆敘述成立嗎？

一般而言，如果 $2^{n-1}\equiv 1\!\!\!\pmod{n}$, 那麼 $n$ 就是質數。然而，有例外： $561=3\cdot 11\cdot 17$ 為一合成數，但 $2^{560}\equiv 1\!\!\!\pmod{561}$。怎麼知道的呢？且看下面的分析：因 $560\equiv 0\!\!\!\pmod{2}$, 故 $2^{560}\equiv 2^0\equiv 1\!\!\!\pmod{3}$。同樣地，因 $560\equiv 0 \!\!\!\pmod{10}$ 且 $560\equiv 0\!\!\!\pmod{16}$, 所以 $2^{560}\equiv 1\!\!\!\pmod{11}$ 且 $2^{560}\equiv 1\!\!\!\pmod{17}$。將此三同餘式合併可得(為什麼？) $$2^{560}\equiv 1\!\!\!\pmod{561}\hbox{。}$$

另一個例外是 $1105=5\cdot 13\cdot 17$。滿足 $a^n\equiv a\!\!\!\pmod{n}\forall a$ 的合成數 $n$ 稱之為 Carmichael 數。這種數極其稀少，但卻有無限多個[2]。 雖然如此，這些例外在實作上是相當罕見的。因此，如果 $2^{n-1}\!\equiv\! 1\!\!\!\!\pmod{n}$ 那麼非常有可能 $n$ 是一個質數。

前面十個 Carmichael 數為 $$561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341,\cdots\hbox{。}$$ 將這十個 Carmichael 數分解後如下：

In[17]:=FactorInteger[{561,  1105,  1729, 2465, 2821, 6601,
                      8911, 10585, 15841, 29341}]
Out[17]={{{3,1},{11,1},{17,1}},{{ 5,1},{13,1},{17,1}},
         {{7,1},{13,1},{19,1}},{{ 5,1},{17,1},{29,1}},
         {{7,1},{13,1},{31,1}},{{ 7,1},{23,1},{41,1}},
         {{7,1},{19,1},{67,1}},{{ 5,1},{29,1},{73,1}},
         {{7,1},{31,1},{73,1}},{{13,1},{37,1},{61,1}}}

觀察得到所有這十個 Carmichael 數都是三個相異質數的乘積， 但不要誤以為這是 Carmi-chael 數的特性，因為 $$62745=3\times5\times47\times89$$ 是一個具有四個質因子的 Carmichael 數。然而不難證明所有的 Carmichael 數至少有下列兩個特性：

• 每一個 Carmichael 數都是奇數。
• 每一個 Carmichael 數都是相異質數的乘積。

費馬小定理反逆敘述

當然，如果 $2^{n-1}\not\equiv 1\pmod{n}$, 則 $n$ 不可能是質數。因為計算 $2^{n-1}\pmod{n}$ 的速度奇快無比 (見第 9 節) ，這提供了我們一個尋找質數的方法。 即，選取一起始點 $n_0$ 並連續測試每一個大於 $n_0$ 的奇數 $n$, 看看是否 $2^{n-1}\equiv 1\pmod{n}$ ？若 $n$ 無法通過此測試，那麼就丟掉此數並進行下一個 $n$。當一個 $n$ 通過此測試時，再使用更細膩的技巧來測試 $n$ 的不可分解性。此法之優點在於其整個演算過程遠比去分解每個 $n$ 要快許多，尤其是能很快的將許多的 $n$ 刪除。當然，還有辦法可用來加速整個尋找的過程， 譬如說可先將包含有小質數因子的 $n$ 刪除，然後再進行上述的方法。

對合成數$n$我們亦需要類似費馬小定理的結果。令$\phi(n)$ 為比$n$小且與$n$互質之正整數的個數。例如，$n=10$ 則有四個這種整數，即 1, 3, 7, 9。 因此，$\phi(10)=4$。若 $p$ 為一質數而 $n=p^r$，則除了 $p$ 的倍數 (也就是 $p, 2p, 3p,\cdots p^{r-1}\cdot p$) 之外，其餘的數皆與 $n$ 互質。因此， $$\phi(p^r)=p^r-p^{r-1}=\left(1-\frac{1}{p}\right)\,p^n \hbox{。}$$ 特別而言， $$\phi(p)=p-1\hbox{。}$$ 更一般地，可由孫子定理推論得知(試證明之！)對任何正整數 $n$, $$\phi(n)=n\prod_{pn}\left(1-\frac{1}{p}\right)\hbox{，}$$ 此處的乘積個數乃整除 $n$ 之相異質數的個數。當 $n=pq$ 為兩相異質數的乘積時，則 $\phi(pq)=(p-1)(q-1)$。

在數學運算大師 MATHEMATICA中與此有關的指令如下：

• EulerPhi[$n$] 比 $n$ 小且與 $n$ 互質之正整數的個數，亦即 $\phi(n)$。

In[18]:= EulerPhi[1000]
Out[18]= 400

歐拉定理: 若 $\gcd(a,n)=1$, 則 $a^{\phi(n)}\equiv 1\pmod{n}\hbox{。}$

注意: 當 $n=p$ 為一質數，則歐拉定理 $=$ 費馬小定理。

例題22: 試問 $7^{803}$ 的最後三位數為何？

解: 所要求的乃是被 1000 除的餘數，因此我們必須在模 1000 之下工作。因為 $\phi(1000)=1000\left(1-\frac{1}{2} \right)\left(1-\frac{1}{5}\right)=400$, 所以 $$7^{803}=(7^{400})^2\cdot 7^3\equiv 1^2\cdot 343=343 \pmod{1000}\hbox{。}$$

因此 $7^{803}$ 的最後三位數為 $343$。

注意: 在此我們可將次冪由 $803$ 改為 $3$, 因 $803\equiv 3\!\!\!\!\pmod{\phi (1000)}$。

基本原理: 在模 $n$ 下工作時，次冪的地方必須在模 $\phi(n)$ 之下運作。

這個極其重要的原理我們會一再的使用。 所以要好好的思考上面的那些例子， 直到你自己確信在次冪的地方一定要模 $400=\phi(1000)$ 才算完成正確 (也就是說，不要去當那許許多多的大傻瓜，錯誤地試著將次冪放在模 1000 之下來運作)。

先觀察一下，在模 11 之下 7的次冪：

一眼即可看出，在模 11 之下所有非零元素都是 7 的次冪。此種元素 7 稱之為模 11 的一個原根(primitive root)^{12 12} 「乘法生成元素(multiplicative generator)」 可能更傳神，但不普遍為人採用。。同樣地， 每一個模 23 的非零元素都是 5 的次冪，所以 5 是模 23 的一個原根。然而， $2^{11}\equiv 1\pmod{23}$, 所以只有 1, 2, 4, 8, 16, 9, 18, 13, 3, 6, 12 是 2 的次冪。因此 2 不是模 23 的一個原根。模 23 的原根有 5, 7, 10, 11, 14, 15, 17, 19, 20, 21。

一般而言，當 $p$ 為一質數，模 $p$ 的一個原根就是其中一個非零元素 $g$ 使得每一個模 $p$ 的非零元素都是 $g$ 的一個次冪。每一個質數 $p$ 都有 $\phi(p-1)$ 個原根。特別而言，至少有一個原根。 在實作上，如果知道 $p-1$ 的分解式，那麼要找到一個原根並不難。見一般習題 8。

在數學運算大師 MATHEMATICA 中與此有關的指令如下：

• PrimitiveRoot[p]^{13 13} 下達這個指令前，需先載入 「Number Theory」的套裝軟體如前面In[14]所示。 給予質數模 $p$ 之下的最小原根。 ( $p$ 也可能是一奇質數的次冪或是一奇質數次冪的兩倍)

In[19]:= PrimitiveRoot[{65537,11,23}]
Out[19]= {3,2,5}

我們將密碼學當中所要用到原根方面的主要結果摘要在此。

定理: 令 $g$ 為質數 $p$ 的一個原根。

• 若 $n$ 為一整數，則 $g^n\equiv 1\pmod{p}\iff n\equiv 0\pmod{p-1}$。
• 若 $j$ 與 $k$ 為二整數，則 $g^j\equiv g^k\pmod{p}\iff j\equiv k\pmod{p-1}$。

證明: 若 $n\equiv 0\pmod{p-1}$, 則存在一整數 $m$ 使得 $n=(p-1)m$。

因此透過費馬小定理，我們有 $$g^n\equiv (g^m)^{p-1}\equiv 1 \pmod{p}\hbox{。}$$ 相反地，假設 $g^n\equiv 1\pmod{p}$。我們要證明 $p-1$ 整除 $n$。很自然地，我們將 $n$ 除以 $p-1$ 得到 $n=(p-1)q+r$, 其中 $0\le r\lt p-1$。我們有 $$1\equiv g^n\equiv (g^q)^{p-1}g^r\equiv 1 \cdot g^r\equiv g^r \pmod{p}\hbox{。}$$ 假設 $r>0$。考慮所有 $g\pmod{p}$ 的次冪即可察覺，我們頂多就只有 $r$ 個元素。但 $r\lt p-1$, 因此並非所有模 $p$ 之下的非零元素都是 $g$ 的一個次冪。這與 $g$ 是原根的假設矛盾。剩下來唯一的可能性是 $r=0$。所以 $n=(p-1)q$, 也就是 $p-1$ 整除 $n$。這證明了第一部份。

對第二部份，假設 $j\ge k$ (否則將 $j$ 與 $k$ 對調)。我們有 $$g^j\equiv g^k\iff g^{j-k}\equiv 1\iff j-k\equiv 0\iff j\equiv k\pmod{p-1}\hbox{。}$$

10. 模 $n$ 之下的逆方陣 根據模 $n$ 之下的除法原理，我們知道求模 $n$ 之下的逆方陣可用一般求逆方陣的方法來完成。 所需要的基本事實如下：

基本事實: 在模 $n$ 之下，方陣 $M$ 是可逆的 $\iff \gcd(\det(M),n)=1$。

在此我們僅處理小方陣 (2或3階) ，此乃因為在我們所要介紹的密碼學當中這已綽綽有餘。 在這種情況之下，求模 $n$ 之下的逆方陣最容易的方式就是使用有理數，然後再轉換回模 $n$ 之中的數。眾所週知，一個佈於整數的方陣其逆方陣可寫成另一佈於整數的方陣除以其行列式值。 因為我們假設其行列式值與 $n$ 互質，所以可求出此行列式值的乘法反元素。例如在 $2\times 2$ 的情況中，一般的公式為 $$\pmatrix{a &b\cr c &d}^{-1}=\frac{1}{ad-bc}\pmatrix{d & -b\cr -c &a},$$ 所以我們需要求出 $ad-bc$在模 $n$之下的乘法反元素。

例題23: 試求 $\pmatrix{1 &2\cr 3 &4} \pmod{11}$ 的逆方陣。

解: 因為 $ad-bc=-2$ 在模 11 之下的乘法反元素為 5 ，所以我們可將 $-\frac{1}{2}$ 用 5 來代換得到 $$\pmatrix{1&2\cr 3&4}^{-1}\equiv -\frac{1}{2} \pmatrix{\ \ 4 &-2\cr -3 &\ \ 1}\equiv 5\pmatrix{\ \ 4&-2\cr -3&\ \ 1} \equiv\pmatrix{9&1\cr 7&5}\pmod{11}\hbox{。}$$

驗算如下，得知無誤： $$\pmatrix{1 &2\cr3 &4} \pmatrix{9 &1\cr 7 &5} \equiv \pmatrix{23 &11\cr 55 &23}\equiv \pmatrix{1 &0\cr 0 &1} \pmod{11}\hbox{。}$$

例題24: 試求 $M=\pmatrix{1&1&1\cr 1&2&3\cr 1&4&9} \pmod{11}$ 的逆方陣。

解: 因為 $\det(M)=2$ 在模 $11$ 之下的乘法反元素為 $6$, 所以我們可將 $\frac{1}{2}$ 用 6 來代換得到 $$M^{-1}\!\!\equiv\! \frac{1}{2}\! \pmatrix{\ \ 6 &-5 &\ \ 1\cr -6&\ \ 8&-2\cr \ \ 2 &-3 &\ \ 1} \!\!\equiv\!6\!\pmatrix{\ \ 6 &-5 &\ \ 1\cr -6&\ \ 8&-2\cr \ \ 2 &-3 &\ \ 1} \!\!\equiv\!\! \pmatrix{3 &3 &\ 6\cr 8&4&10\cr 1 &4 &\ 6} \!\!\!\!\!\!\pmod{11}\hbox{。}$$

為何我們需要行列式值與 $n$ 互質呢？ 假設 $MN\equiv I\pmod{n}$, 此處 $I$ 為單位方陣。則 $$\det(M)\det(N)\equiv\det(MN)\equiv\det(I)=1 \pmod{n}\hbox{。}$$

因此 $\det(M)$ 在模 $n$ 中有乘法反元素，亦即 $\det(M)$ 與 $n$ 必須互質。

例題25: 試求 $M=\pmatrix{13&12&35\cr 41&53&62\cr 71&68&10}\pmod{999}$ 的逆方陣。

解: 若使用 Mod在 Inverse 上，得不到真正的答案：

In[20]:=Mod[Inverse[{{13,12,35},{41,53,62}, {71,68,10}}],999]
Out[20]={{3686/34139, 34102601/34139, 1111/34139},
         {34100869/34139, 2355/34139, 34104232/34139},
         {975/34139, 32/34139, 34104664/34139}}

所以改用 PolynomialMod 在 Inverse 上，則得到答案如下：

In[21]:= PolynomialMod[Inverse[{{13,12,35},{41,53,62},
          {71,68,10}}] ,999]
Out[21]= {{772,472,965},{641,516,851},{150,133,149}}

---本文作者任教於私立東海大學數學系---