發新話題
打印

正整數x除以10、12、14所得餘數都是質數,求x的所有可能解

推到噗浪
推到臉書

正整數x除以10、12、14所得餘數都是質數,求x的所有可能解

x是未滿420的正整數,x除以10、12、14所得餘數分別是r_1、r_2、r_3,且r_1、r_2、r_3為兩兩相異的質數,求x的所有可能解。謝謝!

TOP

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
文不成,武不就

TOP

回復 2# tsusy 的帖子

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

[ 本帖最後由 克勞棣 於 2021-3-26 12:35 編輯 ]

TOP

回復 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 個
文不成,武不就

TOP

回復 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 都恰好對應一組餘數數對,但這與質數有什麼關係?我想不下去了。
盼解惑,再次感謝!

TOP

回復 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)\) 直接構造了解的存在性
文不成,武不就

TOP

發新話題