上頁 12345678910111213 次頁

談韓信點兵問題 (第 12 頁)

蔡聰明

 


首頁 | 搜尋

.原載於科學月刊第二十九卷第九期
.作者當時任教於台大數學系

註釋
對外搜尋關鍵字
 
中國剩餘定理

孫子問題可以再推廣,將三個數3、5、7改成兩兩互質的n個正整數,解法仍然相同。

定理2. 設 m1,m2,…,mnn 個兩兩互質的正整數,則不定方程式
\begin{displaymath}
\left \{
\begin{array}{c}
x = m_1 q_1 +r_1 \\
x = m_2 q_2 +...
...\vdots \\
\vdots \\
x = m_n q_n +r_n \\
\end{array}\right .
\end{displaymath} (27)

存在有解答,並且在取模 m1,m2,…,mn 之下,解答是唯一的。復次,(26) 式的通解等於特解加上齊次方程的通解 註1

證明: 我們只需證明,當 $r_k=1,r_i=0,\forall i\neq k$ 時,(26)式存在有整數解即可。令

\begin{displaymath}
M_k=m_1m_2\cdots m_{k-1}m_{k+1}\cdots m_n
\end{displaymath}

Mkmk 互質。由歐氏算則(即輾轉相除法)知,存在整數 r,s 使得

r Mk+smk=1

有整數解。從而

\begin{displaymath}
r M_k = -sm_k + 1 = 1 \pmod{m_k}
\end{displaymath}

r Mk 即為所求的一個解答。再按線性方程的疊合原理,就可以求得26式的通解了。證畢。

注意:當 m1,m2,…,mn 不兩兩互質時,26式可能無解。

習題2. 請讀者舉出反例。

   

上頁 12345678910111213 次頁

回頁首
 
(若有指正、疑問……,可以在此 留言寫信 給我們。)
EpisteMath

EpisteMath (c) 2000 中央研究院數學所、台大數學系
各網頁文章內容之著作權為原著作人所有


編輯:洪瑛 / 繪圖:簡立欣 最後修改日期:2/17/2002