一個餘數問題ˇ

Question

-----------------------
有三位數，如除以5則餘2，如除以7餘3，如除以9則餘4
求此數?
-----------------------
這題答案是什麼?
這類餘數不規則的題目要怎麼做?

Answer 1

有數n，如除以5則餘p，如除以7餘q，如除以9則餘r,求此數

let n=r*(5*7*a)+p*(7*9*b)+q*(5*9*c) + 5*7*9*k

5*7*a == 1 mod 9
8a == 1 mod 9
-a == 1 mod 9
a=-1

63b == 1 mod 5
3b == 1 mod 5
b=2

45c == 1 mod 7
3c == 1 mod 7
c=-2

==> n=-35r+126p-90q+ 315k
-----------------------
有三位數，如除以5則餘2，如除以7餘3，如除以9則餘4
求此數?
n=315k-35*4+126*2-90*3
=315k-140+252-270
=315k-158
1000>n>99
==> n=315-158, 315*2-158, or 315*3-158
=157, 472 ,or 787
-----------------
這題答案因為餘數是(除數-1)的一半, 所以答案剛好是(除數連乘-1)的一半
=(5*7*9-1)/2=157
其他組就再加除數連乘(315): 157+315=472, 157+315+315=787