Board logo

標題: 正整數x除以10、12、14所得餘數都是質數,求x的所有可能解 [打印本頁]

作者: 克勞棣    時間: 2021-3-25 22:34     標題: 正整數x除以10、12、14所得餘數都是質數,求x的所有可能解

x是未滿420的正整數,x除以10、12、14所得餘數分別是r_1、r_2、r_3,且r_1、r_2、r_3為兩兩相異的質數,求x的所有可能解。謝謝!
作者: tsusy    時間: 2021-3-26 11:36

14以下的質數有3,5,7,11,13,故x的一個可能為
\(\left\{ \begin{array}{l}
x \equiv 3(\bmod {\kern 1pt} {\kern 1pt} {\kern 1pt} 10)\\
x \equiv 5(\bmod {\kern 1pt} {\kern 1pt} {\kern 1pt} 12)\\
x \equiv 7(\bmod {\kern 1pt} {\kern 1pt} {\kern 1pt} 14)
\end{array} \right. \Leftrightarrow \left\{ \begin{array}{l}
x \equiv 3(\bmod {\kern 1pt} {\kern 1pt} {\kern 1pt} 5)\\
x \equiv 2(\bmod {\kern 1pt} {\kern 1pt} {\kern 1pt} 3)\\
x \equiv 0(\bmod {\kern 1pt} {\kern 1pt} {\kern 1pt} 7)\\
x \equiv 1(\bmod {\kern 1pt} {\kern 1pt} {\kern 1pt} 4)
\end{array} \right. \Leftrightarrow x \equiv ( - 84) \cdot 3 + ( - 140) \cdot 2 + 120 \cdot 0 + 105 \cdot 1 \equiv 413(\bmod {\kern 1pt} {\kern 1pt} 420)\)

更一般的情況可寫為
\(\left\{ \begin{array}{l}
x \equiv a(\bmod {\kern 1pt} {\kern 1pt} {\kern 1pt} 5)\\
x \equiv b(\bmod {\kern 1pt} {\kern 1pt} {\kern 1pt} 3)\\
x \equiv c(\bmod {\kern 1pt} {\kern 1pt} {\kern 1pt} 7)\\
x \equiv d(\bmod {\kern 1pt} {\kern 1pt} {\kern 1pt} 4)
\end{array} \right. \Leftrightarrow x \equiv ( - 84) \cdot a + ( - 140) \cdot b + 120 \cdot c + 105 \cdot d(\bmod {\kern 1pt} {\kern 1pt} 420)\)

模10模12模14模5同餘a模3同餘b模7同c模4同餘dx=-84a-140b+120c+105d 模420
3573201413
3511324153
35133261293
3753153103
37113143403
37133163223
31153253383
31173203203
31113326383
5370003315
53110043375
53130063195
5730133115
57110143235
5713016355
51130233395
5117020335
511130263335
7352053327
73112043207
7313206327
753223117
75112241137
75132261377
71132233227
7115225347
711132263167

作者: 克勞棣    時間: 2021-3-26 12:33     標題: 回復 2# tsusy 的帖子

請問「x=-84a-140b+120c+105d 模420」是利用中國剩餘定理嗎?
如果只求符合條件的x有「幾個」,而不管x的實際值,請問有無算式可算出答案是27個?
謝謝!

[ 本帖最後由 克勞棣 於 2021-3-26 12:35 編輯 ]
作者: tsusy    時間: 2021-3-26 19:12     標題: 回復 3# 克勞棣 的帖子

是中國剩餘定理。

算式就是排列組合
模 10, \( r_1 \) 可為 3,5,7
模 12, \( r_2 \) 可為 3,5,7,11
模 14, \( r_3 \)可為 3,5,7,13
且要求兩兩相異,故有 \( (r_1,r_2,r_3) \) 有 \( 3 \times (4-1) \times (5-2) = 27 \) 組
而每一組 \( (r_1,r_2,r_3) \) 都恰好對應一個 \( x \) 的解,故滿足條件的 \( x \) 有 27 個
作者: 克勞棣    時間: 2021-3-26 23:01     標題: 回復 4# tsusy 的帖子

「模 14, r_3可為 3,5,7,13」這一句,寸絲老師是否筆誤少寫了11?

另外再請教,為什麼每一組 (r_1, r_2, r_3) 都恰好對應「一個 」x 的解呢?
(1)為什麼同一組 (r_1, r_2, r_3)不可能對應「2個以上」 x 的解?
(2)為什麼不會有某一組 (r_1, r_2, r_3)對應「0個」 x 的解(亦即沒有任何x可以滿足這組餘數數對)?

對於(1),在下的想法是
設x_1, x_2都滿足某一組 (r_1, r_2, r_3),則易知 |x_1 - x_2 | 是10的倍數(因為它們除以10有相同餘數), 同理,|x_1 - x_2 | 是12的倍數且是14的倍數,
所以 |x_1 - x_2 |是[10, 12, 14]=420的倍數,
但x_1與 x_2被侷限在1,2,3,4,.....,419之中,
所以只能  |x_1 - x_2 |=0,故x_1 - x_2=0,即x_1=x_2,所以一組 (r_1, r_2, r_3)不可能對應「2個以上」 x 的解。

對於(2),在下的想法是
任何一個 x 除以10都恰好有一個餘數,x 除以12、除以14也是一樣恰好有一個餘數,所以任何一個 x 都恰好對應一組餘數數對,但這與質數有什麼關係?我想不下去了。
盼解惑,再次感謝!
作者: tsusy    時間: 2021-3-27 17:16     標題: 回復 5# 克勞棣 的帖子

對,筆誤,漏掉11了

(1) 你證完了
(2) 不知道是否有發現:「質數 2 被我刻意略過了」,因為放入 (2,3,5) 會無解。
另一件事,則是為了解同餘方程,將原本三個的條件,拆解成四個式子了,但實際上是 六個式子,只是其中有三條式子相同。而在 (2,3,5) 的情況,則會得到矛盾的式子,表示無整數解。

\(\left\{ \begin{array}{l}
x \equiv 2(\bmod {\kern 1pt} {\kern 1pt} {\kern 1pt} 10)\\
x \equiv 3(\bmod {\kern 1pt} {\kern 1pt} {\kern 1pt} 12)\\
x \equiv 5(\bmod {\kern 1pt} {\kern 1pt} {\kern 1pt} 14)
\end{array} \right. \Leftrightarrow \left\{ \begin{array}{l}
x \equiv 2(\bmod {\kern 1pt} {\kern 1pt} {\kern 1pt} 5)\\
x \equiv 2(\bmod {\kern 1pt} {\kern 1pt} {\kern 1pt} 2)\\
x \equiv 3(\bmod {\kern 1pt} {\kern 1pt} {\kern 1pt} 3)\\
x \equiv 3(\bmod {\kern 1pt} {\kern 1pt} {\kern 1pt} 4)\\
x \equiv 5(\bmod {\kern 1pt} {\kern 1pt} {\kern 1pt} 7)\\
x \equiv 5(\bmod {\kern 1pt} {\kern 1pt} {\kern 1pt} 2)
\end{array} \right. \)

其中,一個式子對應兩個式子,\( \Leftarrow \) 的理由和(1)相同

沒有質數2的情況,則由 \( x \equiv -84a - 140b + 120c + 105d (mod 420)\) 直接構造了解的存在性




歡迎光臨 Math Pro 數學補給站 (https://math.pro/db/) 論壇程式使用 Discuz! 6.1.0