證明：給定四個質數除數與四個餘數，必有整數x符合該除法

Question

a,b,c,d為四個相異質數，p,q,r,s為四個整數(不見得相異)，且0≦p≦a-1，0≦q≦b-1，0≦r≦c-1，0≦s≦d-1，證明必存在整數x，使得x除以a餘p，且x除以b餘q，且x除以c餘r，且x除以d餘s。比方說我隨便挑四個質數5,11,13,19，再隨便挑四個餘數1,3,4,3，那麼必存在某個整數x，使得x分別除以5,11,13,19，餘數分別是1,3,4,3，儘管x可能很大。經過計算，x最小值是5646這是我最近想到，很有意思的題目。正所謂「江湖一點訣，說破不值三兩錢」，這題可以引用一個原理，跟許多人小時候玩的某個跑來跑去的遊戲相通。

Answer 1

這個問題
可以推廣到任意n個質數

我還可以證明 小樂透的開獎結果
可以表示成6個餘數~

2006-02-13 14:12:56 補充：
取 P1，P2，P3‧‧‧‧，Pn 為 n 個質數
令 R1，R2，R3‧‧‧‧，Rn 表示 某個數X
分別除以 P1，P2，P3‧‧‧‧，Pn 之後的餘數

因為 Rk 屬於整數集合 { 0 ，1，2，3‧‧‧‧Pk-2，Pk-1}
因此 n-序組 (R1，R2，R3‧‧‧‧，Rn) 共有 P1*P2*P3‧‧‧‧*Pn 個元素
然而整數 介於 0 到 (P1*P2*P3‧‧‧‧*Pn - 1) 之間 的數量
恰等於 P1*P2*P3‧‧‧‧*Pn
又 兩個集合A與B若基數相同
則存在一個 Bijection 使得 A中每一個元素 對應B中某一個特定元素~
又 Bijection 必是可逆映射 因此 給定一個 n-序組 (R1，R2，R3‧‧‧‧，Rn)
必有唯一整數 X 介於 0 到 (P1*P2*P3‧‧‧‧*Pn - 1) 之間 滿足
X分別除以 P1，P2，P3‧‧‧‧，Pn 之後的餘數
恰為 R1，R2，R3‧‧‧‧，Rn 。

小樂透開獎結果組合 共有 37*19*17*13*11*7*3 種
那麼 將每個開獎結果對應到 介於 1 到 37*19*17*13*11*7*3 之間的個數
而 1 到 37*19*17*13*11*7*3 之間的個數
又可以 用分別除以 37 19 17 13 11 7 3 之後的餘數組表示~~
所以囉~
小樂透每個開獎結果都可以對應到 除以 37 19 17 13 11 7 3 之後的某個餘數組!


以上是由經常產生錯誤的直覺 所推論出的證明~~
希望 真正的高手 能出手幫我解決 盲點~~ 必竟自修所得必有誤解之處~

2006-02-13 14:15:26 補充：
是將每個開獎結果對應到 介於 1 到 37*19*17*13*11*7*3 之間的 整數 才對 不是 個數

2006-02-13 14:58:12 補充：
更正一下 小樂透開獎結果組合 共有 37*19*17*11*7*3 種 才對~~小樂透每個開獎結果都可以對應到 除以 37 19 17 11 7 3 之後的某個餘數組~~

2006-02-14 08:55:13 補充：
bijection 就是一對一映成映射~
小樂透是 38選6
每一注 都是從38個號碼中選6個~

Answer 2

天下戰區: ＧＯ.ｔｓａ９９.ｎｅｔ

電子機台．真人遊戲和你一同玩樂
麻將 百家樂 5PK 德州撲克 水果盤 賓果 ..
輪盤 21點 10點半 骰盅 牌九 鬥地主 13支

只要免費註冊會員首次儲值送10%還有<讀卡機>

透過網路AD廣告的朋友可以按此領取免費點數

網址: ＧＯ.ｔｓａ９９.ｎｅｔ
24H客服等待為您服務!

Answer 3

1.這題其實除數不一定要是質數，只要兩兩互質即可，寫質數是故意要誤導思考方向的.....哈哈
2.青蛙的費馬小定理用得真漂亮(差點以為你亂寫)，不過還是沒脫離中國剩餘定理的影子，我主觀地希望，這題不要用中國剩餘定理，而是集合元素對應的存在性證明，既然你要我不選你，那我就遵照辦理好了。
倒是如果除數不是質數，就要用更一般的Fermat-Euler定理了。

2006-02-14 00:34:00 補充：
我的想法大致和砌雲風一樣(不過他的數學程度比我好太多了)，我想的是：
考慮0到(除數乘積-1)這些數
1.每一個數都對應到"唯一一個"除數組
2.每一個除數組都不可能對應到2個以上範圍內的數

第1點是蠻trivial的，難道x除以3會餘1且餘2嗎？
第2點，若不然，則該除數組所對應到的2個x，其差為除數乘積的倍數，則至少一個x會落到範圍外，矛盾。

所以每一個除數組對應到0或1個範圍內的數。
對應到0個(沒有對應到任何數)有可能嗎？有的，若除數不兩兩互質時，例如x除以3,4,6，餘1,2,3，這個x就不存在。

2006-02-14 00:35:03 補充：
好，現在問題是，當除數兩兩互質時，為何每一個除數組都不會發生對應不到數的情形呢？
關於這點，我想砌雲風的解釋是對的(雖然以我的程度看不懂bijection是什麼東西)，但是這題有一個更直觀的定理可以用，和我說的那個跑來跑去的遊戲相通。

2006-02-14 00:39:15 補充：
我說的那個跑來跑去的遊戲，不是小樂透喔！會用到椅子啦！
話說回來，小樂透是這樣玩嗎？怎麼跟我知道的不一樣？可以說一下實際玩法嗎？

2006-02-15 00:20:40 補充：
原來你約分過了

Answer 4

正所謂「江湖一點訣，說破不值三兩錢」 呱呱!!
公式給他灌下去 就真的不值錢啦~ 呱!!
取
X = p*(bcd)^(a-1) + q*(acd)^(b-1) + r*(abd)^(c-1) + s*(abc)^(d-1) MOD abcd

還需要證明嗎? 呱呱!!

千萬別選我 選別人 呱!!

Answer 5

so do it, not just adress that U can do it... Dont say it, but do it... willing to learn it...

Answer 6

大衍求一術?