Re: [中學] 國中餘數

[paggei (XD)]

※ 引述《callmedance (中和梁烈唯)》之銘言：
: 請教兩題餘數問題
其實也可以考慮中國餘數定理...雖然丟在高中，不過只是運用的話國中應該也OK
: 1. n為自然數，除以5餘1，除以7餘2，除以11餘3  求n的最小值(四位數字)
把n分成三個分工合作的部份：n = a + b + c
a負責除以5餘1的任務，b負責除以7餘2、c負責除以11餘3

但是互相之間又不能影響，否則加起來後餘數會有變動。
因此a除以7、11的餘數都要是0 -> 77的倍數，就不會對除以7、除以11的情況有所影響。
可以找到
   a = 77 x 3 = 231
同理
   b = 55 x 5 = 275
   c = 35 x 7 = 245 (紅色的部份只要看x1時的餘數去算就好)

這時 a + b + c = 751 同時滿足除以5餘1，除以7餘2，除以11餘3三個條件。
因為題目要求要四位數，所以加上5, 7, 11的最小公倍數385
-> 751 + 385 = 1136即為所求

: 2. n為自然數，除以11餘1，除以9餘6，除以7餘5  求n的最大值(四位數字)
同理，a負責除以11餘1，除以9、7都要是0
      b負責除以 9餘6，除以11、7都要是0
      c負責除以7餘5，除以9、11都要是0

  -> a = 63 x 7 = 441
     b = 77 x 3 = 231
     c = 99 x 5 = 495

  -> 滿足條件者為a + b + c = 1167，且加上最小公倍數693的倍數皆為所求
  -> 最大者為9483

: 餘數苦手 ~"~
: 對於多項式的餘式問題還好，這種餘數問題就很沒概念
: 不知道可以怎麼加強?

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 163.26.109.229
推 callmedance :這就是多項式朗格朗日假設法耶 @@  原來可以這樣用
→ callmedance :這次發問真的學到好多  謝謝這位老師
→ paggei      :因為拉格朗日多項式就是從牛頓插值多項式衍伸來的XD
→ paggei      :所以這跟上篇兩個方法本來就是連貫的啊～