代數解餘數問題 (Andy 奇想)

http://4rdp.blogspot.com/2018/09/andy.html

今年暑假 Andy 有一奇想，用代數解餘數問題，以往大家用中國餘式定理解題，他自己想另外方法來解，今記錄下來。

例題，一籃橘子，三個一堆餘一，五個一堆餘二，七個一堆餘三，十一個一堆餘五，請問總共最少多少個橘子？

假設橘子數量  x = 3a+1 = 5b+2 = 7c+3 = 11d+5
則  3a = 5b+1,  5b = 7c+1,  7c = 11d+2
3a = 5b+1    最小值  a = 2, b = 1
5b = 7c+1    最小值  b = 3, c = 2
7c = 11d+2   最小值 c = 5, d = 3

令 a = 2+5n,   b = 1+3n
令 b = 3+7m,  c = 2+5m
令 c = 5+11k,  d = 3+7k


3(2+5n) = 5(3+7m)+1
3n = 7m+2     最小值 n = 3, m = 1
5m = 11k+3    最小值 m = 5, k = 2

令 n = 3+7p,  m = 1+3p
令 m = 5+11q,  k = 2+5q

3p = 11q+4     最小值 p = 5, q = 1

把 p,q 值反帶回上式
n = 38,  m = 16,  k = 7

把 n,m,k 值反帶回上式
a = 192,  b = 115, c = 82,  d = 52

所以  x = 577


我觀察 Andy 從小就很喜歡二元一次整數解問題，訓練數學感 3 ─ 好難的小二數學 他的解法就是代值試算，所以本題最小值解的部分就是他從小的習慣，不過這要迭代很多次才能得值，解法蠻直觀，就先記錄下來。