Re: [解題] 高一數學 餘數 韓信點兵

[Cactuss16 (Cake & Toast)]

※ 引述《Cactuss16 (Cake & Toast)》之銘言：
: 1.年級：高一
: 2.科目：數學
: 3.章節：整數、餘數
: 4.題目：韓信點兵，每 7人一數餘 6, 11人一數餘 5, 13人一數餘 4
:         問士兵最少有幾人？
:         解：797 人
: 5.想法：
: 點兵的題目，可是餘數不同、不足數也不同，可能要用其他辦法
: 高中有做過，可是臨時想不到怎麼做.... Orz
受益太多了，我試著整理一下...
看到題目一般直覺會以代數寫出
X = 7q1 + 6
  = 11q2 + 5
  = 13q3 + 4
最終要寫成 X = 〔7,11,13〕q + x
           x 以 7,11,13 除之分別餘 6,5,4 也就是士兵最少有幾人

phxcon 版友的想法我不曉得如何直覺說明,
        x = 〔11,13〕b + x2  且  x%7 = 6
        x2= 13c + 4  且  x2%7 = 5
        c 套數字推算 x2，b 再套數字推算 x 得解

ncusnoopy 版友是
        X = 13q1 + 4             ## 由大到小算的次數會比較少
          = 13(11q2 + r1) + 4    ## 想辦法將除數 11 導入式子
                                 ## 且 0<r1<11，說明算10次以內必有解
          = 143q2 + 13r1 + 4     ## (13r1 + 4)%11 = 5,  r1套數字推算為6
          = 143(7q3 + r2) + 82   ## r1=6 帶入,  再將除數 7導入式子,  0<r2<7
          = 1001q3 + 143r2 + 82  ## (143r2 + 82)%7=6,  r2套數字推算為5
                                 ## 此式同等 q3〔7,11,13〕+r2〔11,13〕+13r1 +4
          = 1001q3 + 797

kioskyline 版友則提供了不用套數字的方法
        ex. (13r1 + 4)%11 = 5
         => [(11+2)r1 -1]%11 = 0   ## 11的倍數就不用再管了
         => [2r1+(11-12)]%11 = 0   ## 1沒辦法被 2整除, 所以再借 11
         => 2r1-12=0
         => r1=6

        ex. (143r2 + 82)%7 = 6
         => [(140+3)r2 + 76]%7 = 0       ## 7的倍數不用管了
         => [3r2 + (77-1)]%7 = 0
         => (3r2 - 1)%7 = 0              ## r2=1/3 非整數, 不行
         => [3r2 + (7-8)]%7 = 0          ## 繼續找 8, 15
         => 3r2 - 15 = 0
         => r2 = 5

-------------/自虐分隔線/--------------
有了這個數學方法，似乎就能解決此類題目
若一數，以 123 除之餘 101, 231除之餘 98, 312除之餘 95
        X = 312q1 + 95
          = 312(77q2 +r1) + 95            ## 77=231/(312,231),  0<r1<77
          = 〔312,231〕q2 + 312r1 + 95    ## 312r1 +95 = 231k + 98
                              g.c.d 提出  => 3(104r1-77k) -3 = 0
                              由此知餘數之差必為 g.c.d.的倍數, 才有解
                                          => 104r1-77k = 1
                                          => (27r1-1)%77 = 0
                              1, 78, 155, 232, 309, 386, 463, 540 可被27整除
                                          似乎無更快速解...Orz
                                          => 27r1-540=0
                                          => r1=20
          = 〔312,231〕(41q3 +r2) + 6240 + 95
          = 〔312,231,123〕q3 + 〔312,231〕r2 + 6335
                                      ##    〔312,231〕r2 + 6335 = 123m + 101
                                      =>       3*104*77r2 + 6234 = 123m
                                      =>  3(104*77r2-41m) + 6234 = 0
                                      =>     104*77r2-41m + 2078 = 0
                                      =>    (104*77r2 + 2078)%41 = 0
                                      =>       (22*36r2 - 13)%41 = 0
                                      =>       (11*31r2 - 13)%41 = 0
                                      =>       (11*31r2 - 13)%41 = 0
                                      =>           (13r2 - 13)%41=0
                                      =>  r2=1
          = 〔312,231,123〕q3 + 30359

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 123.193.148.213
※ 編輯: Cactuss16       來自: 123.193.148.213      (08/25 02:52)
推 netneto:好用心...先推一個再來研究
→ Cactuss16:yonex大在本版 5917也有相同的問題討論, 那篇較值得研究
→ Cactuss16:http://hk.geocities.com/goodprimes/SCSunzi.htm
→ Cactuss16:上面網頁也有很多同餘問題的文章, 但有點看不懂 orz
推 yonex:你真的很好學耶  加油喔
→ Cactuss16:以我粗淺的數學背景, 難登大雅之堂. 只希望用粗淺的話
→ Cactuss16:能讓非專業的人聽的懂, 以及體會數學方法的內涵
→ Cactuss16:http://www.mikekong.net/Maths/maths-frame.php
→ Cactuss16:上列網頁的證明很詳細了~