■MOD算術(その3)

[Q]z=17  (mod504)

   z=−4  (mod35)

   z=33  (mod16)

の解を求めよ.

===================================

[A]z=504x+17を第2式に代入すると

 z=504x+17=−4  (mod35)

 504x=−21  (mod35)

 72x=−3  (mod5)→x=1  (mod5)がみつかる.

x=5y+1を第1式に代入すると

 z=504(5y+1)+17=2520y+521

これを第3式に代入すると

  2520y+521=33  (mod16)

  2520y=−448  (mod16)

  315y=−61  (mod2)

y=1 (mod2)であるから,y=2t+1とおくと

 z=2520y+521=5040t+3041

したがって,求める数はz=3041  (mod5040)

===================================