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://mathpro.net/db/) 論壇程式使用 Discuz! 6.1.0