Math Pro 數學補給站's Archiver

時間,讓深的東西越來越深,
   讓淺的東西越來越淺。

克勞棣 發表於 2021-3-25 22:34

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

x是未滿420的正整數,x除以10、12、14所得餘數分別是r_1、r_[size=12px]2[/size]、r_[size=12px]3[/size],且r_1、r_[size=12px]2[/size]、r_[size=12px]3為兩兩相異的質數,[/size]求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)\)

[table=98%][tr][td=1,1,72]模10[/td][td=1,1,72]模12[/td][td=1,1,72]模14[/td][td=1,1,72]模5同餘a[/td][td=1,1,72]模3同餘b[/td][td=1,1,72]模7同c[/td][td=1,1,72]模4同餘d[/td][td=1,1,182]x=-84a-140b+120c+105d 模420[/td][/tr] [tr][td]3[/td][td]5[/td][td]7[/td][td]3[/td][td]2[/td][td]0[/td][td]1[/td][td]413[/td][/tr] [tr][td]3[/td][td]5[/td][td]11[/td][td]3[/td][td]2[/td][td]4[/td][td]1[/td][td]53[/td][/tr] [tr][td]3[/td][td]5[/td][td]13[/td][td]3[/td][td]2[/td][td]6[/td][td]1[/td][td]293[/td][/tr] [tr][td]3[/td][td]7[/td][td]5[/td][td]3[/td][td]1[/td][td]5[/td][td]3[/td][td]103[/td][/tr] [tr][td]3[/td][td]7[/td][td]11[/td][td]3[/td][td]1[/td][td]4[/td][td]3[/td][td]403[/td][/tr] [tr][td]3[/td][td]7[/td][td]13[/td][td]3[/td][td]1[/td][td]6[/td][td]3[/td][td]223[/td][/tr] [tr][td]3[/td][td]11[/td][td]5[/td][td]3[/td][td]2[/td][td]5[/td][td]3[/td][td]383[/td][/tr] [tr][td]3[/td][td]11[/td][td]7[/td][td]3[/td][td]2[/td][td]0[/td][td]3[/td][td]203[/td][/tr] [tr][td]3[/td][td]11[/td][td]13[/td][td]3[/td][td]2[/td][td]6[/td][td]3[/td][td]83[/td][/tr] [tr][td]5[/td][td]3[/td][td]7[/td][td]0[/td][td]0[/td][td]0[/td][td]3[/td][td]315[/td][/tr] [tr][td]5[/td][td]3[/td][td]11[/td][td]0[/td][td]0[/td][td]4[/td][td]3[/td][td]375[/td][/tr] [tr][td]5[/td][td]3[/td][td]13[/td][td]0[/td][td]0[/td][td]6[/td][td]3[/td][td]195[/td][/tr] [tr][td]5[/td][td]7[/td][td]3[/td][td]0[/td][td]1[/td][td]3[/td][td]3[/td][td]115[/td][/tr] [tr][td]5[/td][td]7[/td][td]11[/td][td]0[/td][td]1[/td][td]4[/td][td]3[/td][td]235[/td][/tr] [tr][td]5[/td][td]7[/td][td]13[/td][td]0[/td][td]1[/td][td]6[/td][td]3[/td][td]55[/td][/tr] [tr][td]5[/td][td]11[/td][td]3[/td][td]0[/td][td]2[/td][td]3[/td][td]3[/td][td]395[/td][/tr] [tr][td]5[/td][td]11[/td][td]7[/td][td]0[/td][td]2[/td][td]0[/td][td]3[/td][td]35[/td][/tr] [tr][td]5[/td][td]11[/td][td]13[/td][td]0[/td][td]2[/td][td]6[/td][td]3[/td][td]335[/td][/tr] [tr][td]7[/td][td]3[/td][td]5[/td][td]2[/td][td]0[/td][td]5[/td][td]3[/td][td]327[/td][/tr] [tr][td]7[/td][td]3[/td][td]11[/td][td]2[/td][td]0[/td][td]4[/td][td]3[/td][td]207[/td][/tr] [tr][td]7[/td][td]3[/td][td]13[/td][td]2[/td][td]0[/td][td]6[/td][td]3[/td][td]27[/td][/tr] [tr][td]7[/td][td]5[/td][td]3[/td][td]2[/td][td]2[/td][td]3[/td][td]1[/td][td]17[/td][/tr] [tr][td]7[/td][td]5[/td][td]11[/td][td]2[/td][td]2[/td][td]4[/td][td]1[/td][td]137[/td][/tr] [tr][td]7[/td][td]5[/td][td]13[/td][td]2[/td][td]2[/td][td]6[/td][td]1[/td][td]377[/td][/tr] [tr][td]7[/td][td]11[/td][td]3[/td][td]2[/td][td]2[/td][td]3[/td][td]3[/td][td]227[/td][/tr] [tr][td]7[/td][td]11[/td][td]5[/td][td]2[/td][td]2[/td][td]5[/td][td]3[/td][td]47[/td][/tr] [tr][td]7[/td][td]11[/td][td]13[/td][td]2[/td][td]2[/td][td]6[/td][td]3[/td][td]167[/td][/tr][/table]

克勞棣 發表於 2021-3-26 12:33

回復 2# tsusy 的帖子

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

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

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?

另外再請教,[color=red]為什麼每一組 (r_1, r_2, r_3) 都恰好對應「一個 」x 的解呢?[/color]
(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)\) 直接構造了解的存在性

頁: [1]

論壇程式使用 Discuz! Archiver 6.1.0  © 2001-2007 Comsenz Inc.