34105 n 元數與同餘式組

終極密碼

遊戲規則:本遊戲為猜密碼的遊戲。密碼為0到100之間的其中1個整數,電腦會提示密碼的所在範圍,玩家必須在6次之內猜到密碼才能過關。

★ 終極密碼為0到100之間 ★
您共有六次機會

1. 前言

在 [2] 文中, 作者討論一組循環型的同餘式組問題 $$ \left\{ \begin{array}{l} ab \equiv p\pmod{c}\\ bc \equiv p\pmod{a}\\ ca \equiv p\pmod{b} \end{array}\right. $$ 的質數三元數解 $( a, b, c )$ 存在之充要條件, 並證明了當 $p=1$ 或 $-1$ 時, 同餘式組有唯一解 $( 2, 3, 5 )$ 和 $( 2, 3,7)$。本文目的是簡化 [2, 定理3] 的證明, 並將問題推廣至 $n$ 維的同餘式組, 即對 $i = 1,\ldots, n$, $$ \prod_{j\neq i} a_j\equiv p\pmod{a_i}. $$ 其中 $a_1,\ldots,a_n$ 只須互質。 當 $p =-1$ 時, 我們最少能找到一組解, 當 $p =1$ 時, 最少能找到兩組解。 而且這些解都有一定的規律。當 $n = 4$ 時, 唯一性問題也可清楚討論(請參考定理 3.1 和定理 3.2)。 更進一步地, 我們建立了互質 $n$ 元數解存在的充分必要條件。

2. 解存在的充要條件

若 $a, b, c$ 是互質正整數, 且 $a \lt b\lt c$ , 我們稱 $(a, b, c)$ 為三元數。 在 $a, b, c$ 是質數的假設下, [2] 文作者討論如 (\ref{eq1.1}) 的循環型同餘式組的求解狀況。 他們發現, 當 $p=\pm 1$ 時, 同餘式組只有一組解, 分別是 $(2, 3, 5)$ 和 $(2, 3, 7)$。 但對一般的 $p$, 不同的狀況都可能出現, 同餘式組可能無解, 可能有一組解或二組解、甚至三組解。我們猜想任意多組解均可能出現。 眾所皆知, 在同餘式組中, 中國剩餘定理是最重要的定理:

若 $m_1, m_2,\ldots, m_k$ 是兩兩互質的正整數, 則同餘式組 $$ \left\{ \begin{array}{l} x=b_1\pmod{m_1}\\ x=b_2\pmod{m_2}\\ \cdots\ \ \cdots\\ x=b_k\pmod{m_k} \end{array} \right. $$

有唯一解: $ x= b_1 \theta_1N_1+b_2\theta_2N_2+\cdots +b_k\theta_kN_k \pmod{\theta}$。 其中 $\theta=m_1m_2\cdots m_k$, $\theta_i=\theta/{m_i}$, 而 $N_i$ 是 $\theta_i$ 對 $m_i$ 的乘法逆元素。

這個定理的證明方法, 是先構造 $\theta_iN_i$ 使得 $\theta_iN_i\equiv 1 \pmod{m_i}$, 但對其它的 $m_j$, 則有 $\theta_iN_i\equiv 0 \pmod{m_j}$, 而所求 $x$ 即為眾多 $b_i\theta_iN_i$ 的總和(見 [1])。在本文中, 我們利用這個精神簡化 [2] 文中定理$3$的證明。 值得注意的是, 此處我們不必假設 $a, b, c$ 是質數, 只須假設 $a,b,c$ 兩兩互質, 正如中國剩餘定理的假設。

定理 2.1: 三元數 $(a,b,c)$ 是同餘式組 \begin{equation}\left\{ \begin{array}{l} ab \equiv p \pmod{c} \\ bc \equiv p \pmod{a} \\ ca \equiv p \pmod{b} \end{array}\right. \label{eq1.1} \end{equation} 的整數解若且唯若 $$ p \equiv ab+bc+ca \pmod{abc}. $$

證明:
$(\Leftarrow)$ 顯而易見, 故略。
$(\Rightarrow)$ 由(\ref{eq1.1})式知 $$ ab+bc+ca\equiv ab\equiv p\pmod{c}; $$ $$ ab+bc+ca\equiv bc\equiv p\pmod{a}; $$ $$ ab+bc+ca\equiv ca\equiv p\pmod{b}. $$ 因為 $a$、$b$、$c$ 兩兩互質, 故 $$ ab+bc+ca\equiv p\pmod{abc} .\Box$$

我們定義 $(a_1,a_2,\ldots,a_n)$ 為 $n$ 元數若 $a_1,\ldots,a_n$ 是兩兩互質的 $n$ 個正整數, 且滿足 $a_1\lt a_2\lt \cdots\lt a_n$。

定理 2.2: 若 $(a_1,a_2,\ldots,a_n)$ 為 $n$ 元數, 令 $\gamma=a_1a_2\cdots a_n$, $\Gamma_i=\displaystyle\frac{\gamma}{a_i}$, 則對所有 $i=1,2,\ldots,n$ \begin{equation} \Gamma_i\equiv p\pmod{a_i}\label{eq8.5} \end{equation} 若且唯若 $$ p \equiv \sum^n_{i=1}\Gamma_i \pmod{\gamma} . $$

證明: 明顯若 $p\equiv \sum^n_{j=1}\Gamma_i \pmod{\gamma}$, 則對每一 $a_i$, 有 $p\equiv \Gamma_i \pmod{a_i} $。反過來, 若 $p\equiv \Gamma_i \ \pmod{a_i}$, 則 $$\sum^n_{j=1}\Gamma_j\equiv \Gamma_i\equiv p \pmod{a_i}.$$ 因 $a_1,a_2,\cdots,a_n$ 兩兩互質, 故 $$\sum^n_{j=1}\Gamma_j\equiv p \pmod{\gamma}.\Box$$

3. 4 元數解

定理 3.1: 若 $(a,b,c,d)$ 是 $4$ 元數, 且滿足 $$\left\{\begin{array}{l} abc \equiv 1 \pmod{d} \\ abd \equiv 1 \pmod{c}\\ acd \equiv 1 \pmod{b} \\ bcd \equiv 1 \pmod{a} \end{array}\right. $$ 則 $(a,b,c,d)=(2,3,7,41)$ 或 $(2,3,11,13)$。

證明: 利用以下引理 3.3, 得 $a=2$, $b=3$。又令 \begin{eqnarray} 6c&=&1+kd, \label{eq2.3}\\ 6d&=&1+lc, \label{eq2.2}\\ 2cd&=&1+mb. \label{eq2.1} \end{eqnarray} 從 (\ref{eq2.2})減去(\ref{eq2.3}) , (\ref{eq2.1})減去(\ref{eq2.3}) 後可得: \begin{eqnarray*} d(k+6)&=&c(l+6),\\ d(k+2c)&=&3(m+2c). \end{eqnarray*} 因 $b, c, d$ 兩兩互質且 $b=3$, 所以 $c|(k+6)$, 且 $3|(k+2c)$。令 \begin{eqnarray} k+2c&=&3x, \nonumber\\ k+6&=&cy, \label{eq2.5} \end{eqnarray} 得 $$ 3(x+2)=c(y+2). $$ 故 $3|(y+2)$。從(\ref{eq2.3})知 $k\lt 6$, 以此代入(\ref{eq2.5}), 得 $y\lt 4$, 所以 $y=1$。又從(\ref{eq2.5})知 $$1\leq k=c-6\lt 6.$$ 故 $c=7$ 或 $11$, 即 $k=1$ 或 $5$, 且由 (\ref{eq2.3}) 可得 $d=41$ 或 $13$。因此 $(a,b,c,d)=(2,3,7,41)$ 或 $(2,3,11,13)$。 $\Box$

定理 3.2: 若 $(a,b,c,d)$ 是 $4$ 元數, 且滿足 $$\left\{\begin{array}{l} abc \equiv -1 \pmod{d} \\ abd \equiv -1 \pmod{c} \\ acd \equiv -1 \pmod{b} \\ bcd \equiv -1 \pmod{a} \end{array}\right. $$ 則 $(a,b,c,d)=(2,3,7,43)$。

證明: 與上一定理相似。 $a=2$, $b=3$, 且 \begin{eqnarray*} 6c&=&kd-1, \\ 6d&=&lc-1, \\ 2cd&=& 3m-1. \end{eqnarray*} 又 $k+2c=3x$, $k+6=cy$, 則 $3|(y+2)$。因 $k\lt 6$, 故 $y=1$, 且 $7\leq c\lt 12$, 得 $c=7$, $d=43$。 $\Box$

引理 3.3: 設 $( a, b, c, d )$ 為$4$元數, 滿足 $$ \left\{ \begin{array}{l} abc \equiv p \pmod{d}\\ abd \equiv p \pmod{c}\\ acd \equiv p \pmod{b}\\ bcd \equiv p \pmod{a} \end{array}\right. $$ 若 $abc\gt p\gt -5$, 則 $a=2$, $b=3$, 且 $c\lt 12$。

證明: 令 \begin{equation} \left\{ \begin{array}{l} abc = dk + p \\ abd = cl + p \\ acd = bm + p\\ bcd = an + p \end{array}\right.\label{eq12} \end{equation} 其中 $k, l, m, n$ 均為正整數, 且 $a$, $b$, $c$, $d$, 兩兩互質。 將以上等式兩兩相減, 可得 $abc-abd = dk - cl$, 故 $c ( ab + l) = d ( ab + k )$ , 導致 $ c| (ab + k)$。 同理, 有 $abc - acd = dk - bm$, 且 $b ( ac + m ) = d ( ac + k )$ , 故 $ b| (ac + k)$。 另外, $a ( bc + n ) = d ( bc + k )$ , 得 $ a| (bc + k)$。 令 \begin{eqnarray} ab + k &=& cx ,\label{eq13}\\ ac + k &=& by ,\label{eq14}\\ bc + k &=& az .\label{eq15} \end{eqnarray} 從 (\ref{eq13}) 減去 (\ref{eq14}) 得 $$ c( a + x) = b ( a + y ). $$ 即 $b|( a + x)$, 令 \begin{equation} bs = a + x \label{eq17} \end{equation} 現在, 從 $p\gt -5$ 和 (\ref{eq12}) 知 $$ dk\lt abc + 5\lt abd $$ 故 $k \lt ab$, 代入(\ref{eq13}), 得 $x\lt 2a$, 再代入(\ref{eq17})後, 得 $0\lt s\lt 3$。 若 $s = 2$ , 則從 (\ref{eq17})、(\ref{eq13}) 知 $2b = a + x \lt 3a$, 且 \begin{equation} k = 2bc - ab - ac \lt ab .\label{eq18} \end{equation} 故有 $2bc \lt a(2b+c)$, 即 $c \lt 2b$。 再將 (\ref{eq18}) 代入 (\ref{eq15}), 得 $$ az = 3bc - ab- ac. $$ 因此 $a=3$, $b=4$, $x=5$。 代入(\ref{eq18}), $k = 5c - 12 \lt 12$, 矛盾。故 $s = 1$, 即 $b = a + x \lt 3a$。代入(\ref{eq13}), \begin{equation} k = bc - ab - ac \lt ab .\label{eq19} \end{equation} 再代入 (\ref{eq15}), $az = 2bc - ab - ac $, 故 $a = 2$, $ b = 3$ 或 $5$。 若 $b = 5$, 從 (\ref{eq19}) 得 $c \lt 6$, 矛盾。 故 $b = 3$, 從 (\ref{eq19}) 知 $c \lt 12$。 證畢。 $\Box$

利用定理 2.2 和 引理 3.3, 我們可以得到一個快速求循環型同餘式組的方法。 例如: 如果 $p=2n$ 是一偶數, 且 $1\lt p\lt 30$, 則 $a=2$, $b=3$, 所以 \begin{eqnarray*} 2n &\equiv& 6(c+d)+5cd \pmod{6cd}\\ &\equiv& 6(c+d)-cd \pmod{6cd} \end{eqnarray*} 因此, $$ 2n+cd\equiv 6(c+d) \pmod{6cd}. $$ 故 $cd$ 必為偶數。同餘式組 (\ref{eq8.5}) 無 $4$ 元數解。

4. n 元數解的規律

以此規律進行, 則知 $(2,3,7,43,1807)$ 和 $(2,3,7,43,1805)$ 是同餘式組(\ref{eq8.5})對應著 $p=-1$ 和 $p=1$ 的$5$元數解。 而下一組的$6$元數解, 是 $(2,3,7,43,1807,3263443)$ 和 $(2,3,7,43,1807,3263441)$。

構造數列 $\beta_1=2$, $\beta_2=3$, $\beta_{n+1}=\beta_1\beta_2\ldots \beta_n+1$。 顯然, 數列 $\{\beta_i\}$ 遞增且兩兩互質。

定理 4.1: 對所有 $n\geq2$, 向量 ${\bf \cal{B}}_n:=(\beta_1,\beta_2,\ldots,\beta_n)$ 滿足同餘式組 \begin{equation} \Gamma_{i}({\bf \cal{B}}_n)\equiv -1 \pmod{\beta_i},\qquad i=1,2,\ldots,n,\label{eq2.7} \end{equation} 其中 $\Gamma_{i}({\bf \cal{B}}_n)= \prod_{j\neq i}{\bf \cal{B}}_{n,j}$, 而 ${\bf \cal{B}}_{n,j}$ 是向量 ${\cal B}_n$ 的第 $j$ 項。又令 ${\bf \cal{A}}_n:= (\beta_1,\beta_2,\ldots,\beta_{n+1}-2)$, 若 ${\bf \cal{A}}_n $ 滿足同餘式組, 則 \begin{equation} \Gamma_{i}({\bf \cal{A}}_{n})\equiv 1\pmod{{\bf \cal{A}}_{n,i}},\qquad i =1,2,\ldots,n. \label{eq2.8} \end{equation}

證明: 利用數學歸納法。當 $n=2$ 時, ${\bf \cal{B}}_2=(2,3)$; 當 $n=3$ 時, ${\bf \cal{B}}_3=(2,3,7)$, 已知命題成立。假設命題對 $n=k$ 成立, 即 $$\Gamma_{i}({\bf \cal{B}}_k)\equiv -1 \pmod{\beta_i},\qquad i=1,2,\ldots,k.$$ 則對 $i=1,2,\ldots,k$, \begin{eqnarray*} \Gamma_{i}({\bf \cal{B}}_{k+1})&=&\Gamma_{i}({\bf \cal{B}}_k)\cdot \beta_{k+1}\\ &\equiv&(-1)\cdot \beta_{k+1} \pmod{\beta_i}\\ &\equiv&-1\pmod{\beta_i}. \end{eqnarray*} 又 \begin{eqnarray*} \Gamma_{k+1}({\bf \cal{B}}_{k+1})&\equiv&\beta_1\beta_2\cdots\beta_k \pmod{\beta_{k+1}},\\ &\equiv&-1\pmod{\beta_{k+1}}. \end{eqnarray*} 同理, 也有 $\Gamma_{i}({\bf \cal{A}}_{k+1})\equiv 1\pmod{{\bf \cal{A}}_{k+1,i}} $, 其中, $i=1,2,\ldots,k+1$。定理得證。 $\Box$

另外, 我們還找到另一規律, 已知 $(2,3,11,13)$ 是對應 $p=1$ 的 $4$ 元數解, 容易得知 $11 = 2\cdot 6 - 1$ , $13 = 2\cdot 6 + 1$。 以此規律, 得知 $(2,3,7,83,85)$, $(2,3,7,43,3611,3613)$ 也是同餘式組(\ref{eq8.5})對應於 $p=1$ 的 $5$ 元數解和 $6$ 元數解。從而引伸出以下定理。

定理 4.2: 考慮 $(n + 2)$ 元數 ${{\bf \cal{C}}_{n+2}} = ( \beta_1,\beta_2,\ldots, \beta_n, 2\gamma-1, 2\gamma+1 )$, 其中 $\gamma = \beta_1\beta_2\cdots \beta_n$。 則有 $$ \Gamma_i({\bf \cal{C}}_{n+2})\equiv 1\pmod{{\bf \cal{C}}_{n+2,i}} $$ $i=1,\ldots,n+2$。

證明: 當 $n=1$ 時, ${\bf \cal{C}}_3= (2,3,5)$, 命題成立。事實上, 對任意 $n\geq 1$, 若 $1\leq i\leq n$, 由定理 4.1 知 $$ \Gamma_i({\bf \cal{C}}_{n+2})\equiv (-1) (-1)\cdot 1\equiv 1\ \pmod{\beta_i}. $$ 另外, $$ \Gamma_{n+1}({\bf \cal{C}}_{n+2})\equiv 2\gamma \equiv 1\pmod{2\gamma-1};\quad \Gamma_{n+2}({\bf \cal{C}}_{n+2})\equiv -2\gamma \equiv 1\pmod{2\gamma +1}. $$ 由數學歸納法, 定理得證。 $\Box$

後記: 此論文是97學年度中山大學應用數學系高高屏數學科高中科技人才培育計畫高三班專題研究課程之部份成果, 感謝教育部中教司對本研究的補助。

參考資料

華羅庚, 從孫子的神奇妙算談起, 見『華羅庚科普著作選集』, 凡異出版社, 2002年。 羅春光、洪劭軒、黃拓儒, 質數三元數和同餘式組, 數學傳播季刊, 第21卷, 第二期(1997), 66-70。

---本文作者許家甄是中山大學附屬中學高三生; 李昱宏是高雄中學高三生; 潘信鴻是高雄市立中正高中高三生; 何青翰是高雄師範大學附屬中學高三生; 徐含馥是屏東女中高三生; 羅春光是中山大學應用數學系教授。---

文章 推薦

電腦模擬與賭局

假設玩家A和B進行賭博。玩家A有m元,玩家B則有n元,然後擲1個公正的硬幣。如果出現正面就算玩家A贏,反面就算玩家B贏。每次賭注都是1元,如果A贏則A變m+1元、而B變n−1元,並稱此為1回合。雙方不斷地進行賭博,直到某方的錢歸零為止。在這個賭博中,有以下兩個問題:(1)玩家A和玩家B贏的機率各是多少?(2)每投1次硬幣決勝負,都稱為1回合,平均要幾回合,賭局才會結束(某方錢輸光)?....閱讀更多