歡迎訂閱 高中數學數位學習電子報
學習數學有何用處？
有很多，其中之一是，「活化思考、提升效率」。
有人說數學家很懶，這句話是對的，也不對。
的確，數學家總是會想出一些方式，讓工作輕鬆。
然而，他們在思考方法的過程，卻也異常辛苦。
你是否聽過韓信點兵的故事？
韓信，大約是公元前231年－公元前196年的人物，漢高祖劉邦的得力將領。
歷史上著名的軍事家和謀略家。
他在楚漢戰爭中為劉邦建立漢朝立下了汗馬功勞，被譽為「漢初三傑」之一。
韓信在指揮作戰方面有卓越的才能，特別擅長用兵，常常出奇制勝，為後人所傳頌。
我認為，他可能也有數學家的潛質在裡面。
傳說有一次，韓信被要求點清全軍的士兵數量，但士兵數量龐大，難以直接點清。
怎麼辦？
慢慢數，太沒效率了！
韓信便運用了巧妙的數學方法，利用士兵們的排列順序和餘數來計算總數。
如果我們已經知道，士兵人數介於 \(900 \sim 1000\) 人之間。
當然實際人數不會這麼少，你可以再乘以100。這邊為了方便說明起見，先做此假設。
韓信將士兵分成若干小隊，每隊分別以不同的方式排列，
然後記錄每種排列方式下剩餘的士兵數量。具體過程如下：
三人一排： 韓信先將士兵三人一排地排列，記下剩餘的士兵數量。
五人一排： 然後，他將士兵五人一排地排列，再次記下剩餘的士兵數量。
七人一排： 最後，他將士兵七人一排地排列，記下剩餘的士兵數量。
根據這些排列後剩餘的士兵數量，韓信利用數學計算，得出了士兵的總數。
用現代的符號來寫，假設士兵人數有 \(x\) 人，則
\begin{cases}
x\equiv 2 \ \ (mod\ 3) \\
x\equiv 3 \ \ (mod\ 5) \\
x\equiv 2 \ \ (mod\ 7)
\end{cases}
相信解這道題，同學不會有太大的困難，我們再來複習一下：令 $$ x=3a+2=5b+3=7c+2 $$ 其中 \(a,b,c\) 為整數。
接著兩個兩個式子處理：因為 \(x=3a+2 = 5b+3\)，所以 \(x=15d+8\)。
也就是說，先找出 \(3,5\) 的最小公倍數，再找出「被3除餘2」且「被5除餘3」的最小正整數。
比較好的做法是，先列出被5除餘3的正整數，然後再從這些正整數中找到被3除餘2的數字。
很快地，就能找到這個數為 \(8\)。
接著由 \(x=15d+8\) 及 \(x=7c+2\)，找到同時「被15除餘8」及「被7除餘2」的正整數。
同樣地，先求 \(15\) 與 \(7\) 的最小公倍數 \(105\)。
然後最出幾個被15除餘8的正整數：8、23、38、…
再從這些正整數中，找到被7除餘2的正整數。
找到了，這個數就是23。
因此寫出通解為 $$x=105e+23$$
因為人數介於 \(900 \sim 1000\) 人之間，由通解可推得為 \(968\) 人。
這個方法還不錯，但是不容易推廣，也就是說，如果有 \(n\) 個方程式，要如何處理？
\begin{cases}
x \equiv b_1 \ \ (mod \ m_1) \\
x \equiv b_2 \ \ (mod \ m_2) \\
x \equiv b_3 \ \ (mod \ m_3) \\
\ \ \ \ \ \vdots \\
x\equiv b_n \ \ (mod \ m_n)
\end{cases}
其中 \(b_1,b_2,…,b_n\) 為正整數，\(m_1,m_2,…,m_n\) 為兩兩互質的正整數。
我們先看兩個方程式的情形
\begin{cases}
x \equiv b_1 \ \ (mod \ m_1) \\
x \equiv b_2 \ \ (mod \ m_2)
\end{cases}
因為現在是以符號呈現，所以似乎也沒辦法用上述的做法。
但是我們知道，最後是 mod \(m_1\cdot m_2\)
先說答案吧，這個解的形式會是 $$x=b_1m_2x_1+b_2m_1x_2$$ 其中 \(x_1, x_2\) 分別為方程式 $$m_2x_1\equiv 1 \ (mod \ m_1)$$ 及 $$m_1x_2\equiv \ 1 \ (mod \ m_2)$$ 的解。
並且可以驗證，這個方程式存在唯一解 $$x\equiv b_1m_2x_1+b_2m_1x_2 \ (mod \ m_1m_2)$$
可以輕易看出來，這的確是方程式的解。接著我們來驗證解的唯一性：
設有另一解 \(x’\equiv b_i \ (mod \ m_i)\)，其中 \(i=1,2\)
因為 \(x\equiv b_i \ (mod \ m_i)\)，所以 \(x\equiv x’ \ (mod \ m_i)\)
也就是說，$$m_i | x-x’, i=1,2$$
因此 $$m_1m_2 | x-x’$$ 即 $$x\equiv x’ \ (mod \ m_1m_2)$$
有了這個方法，我們將其推廣到一般的情形：方程式
\begin{cases}
x \equiv b_1 \ \ (mod \ m_1) \\
x \equiv b_2 \ \ (mod \ m_2) \\
x \equiv b_3 \ \ (mod \ m_3) \\
\ \ \ \ \ \vdots \\
x\equiv b_n \ \ (mod \ m_n)
\end{cases} 存在唯一解 $$x=M_1b_1x_1+M_2b_2x_2+…+M_nb_nx_n \ (mod \ M)$$
其中 $$M=m_1m_2\cdots m_n$$ 且 $$M_i =\frac{M}{m_i}, i=1,2,\cdots, n $$
並且 \(x_i, i=1\cdots n\) 是方程式 \(M_ix_i\equiv 1 \ (mod\ m_i)\) 的根。
顯然，
$$\begin{aligned}
x &= b_1M_1x_1+b_2M_2x_2+\cdots +b_n M_nx_n \\
&\equiv 0+0+\cdots+0+b_i+0+\cdots+0 \ (mod\ m_i) \\
&\equiv b_i \ (mod\ m_i)
\end{aligned}$$
再寫一次唯一性：
設 $$x’\equiv b_i \ (mod \ m_i)$$
因為 \(x\equiv b_i\ (mod \ m_i)\)，所以 \(x\equiv x’\ (mod\ m_i)\)
也就是說 $$m_i | x-x’, i=1,2,\cdots,n$$
因此 $$M|x-x’$$ 即 $$x\equiv x’\ (mod\ M)$$
最後，再回來看看以下方程式要怎麼解？
\begin{cases}
x\equiv 2 \ \ (mod\ 3) \\
x\equiv 3 \ \ (mod\ 5) \\
x\equiv 2 \ \ (mod\ 7)
\end{cases}
此方程式的解為 $$x\equiv M_1b_1x_1+M_2b_2x_2+M_3b_3x_3\ (mod \ 105)$$
其中 $$M_1=\frac{105}{3}=35, \ M_2=\frac{105}{5}=21, \ M_3=\frac{105}{7}=15$$
代入數字，解可以寫成 $$x\equiv 35\times 2 \times x_1+21\times 3 \times x_2 + 15\times 2 \times x_3\ (mod \ 105)$$
我們可以將問題轉換成解方程式
\begin{cases}
35x_1\equiv 1 \ \ (mod\ 3) \\
21x_2\equiv 1 \ \ (mod\ 5) \\
15x_3\equiv 1 \ \ (mod\ 7) \\
\end{cases}
解得
\begin{cases}
x_1\equiv 2 \ \ (mod\ 3) \\
x_2\equiv 1 \ \ (mod\ 5) \\
x_3\equiv 1 \ \ (mod\ 7) \\
\end{cases}
最後寫出其解 $$x=35\times 2\times 2 + 21\times 3\times 1 + 15\times 2\times 1=233 \equiv 23 \ \ (mod \ 105)$$
這篇文章就先寫到這邊，同學剛好可以藉這個機會熟悉同餘的符號及同餘方程式。
祝一切順利，期末all pass，學習愉快。
No comments! Be the first commenter?