■MOD算術(その4)

[Q]z=17  (mod504)

   z=−4  (mod35)

   z=33  (mod16)

の解を求めよ.

504=8・9・7,35=5・7であるから,この問題は

[Q]z=17  (mod8)

   z=17  (mod9)

   z=17  (mod7)

   z=−4  (mod5)

   z=−4  (mod7)

   z=33  (mod16)

と同等である.

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

[A]z=17  (mod8)→z=8x+17

ここで,x=2t+2を取るとすると

z=8x+17=8(2t+2)+17=16t+33となり,第6式を満たす.

   z=17  (mod7)→z=7x+17

ここで,z=7(x+3)−4と変形すると

   z=−4  (mod7)

となるので,

[Q]z=17  (mod9)

   z=−4  (mod5)

   z=−4  (mod7)

   z=33  (mod16)

n帰着された.

ここで,z=17  (mod9)→z=9x+17を第2式に代入すると

  9x=−21  (mod5)

  x=1  (mod5)

がみつかる.

 x=5y+1をz=9x+17に代入すると

  z=45y+26

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

  45y+26=−4  (mod7)

  45y=−30  (mod7)

  y=4  (mod7)

がみつかる.

 y=7t+4をz=45y+26に代入すると

  z=315t+206

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

  315t+206=33  (mod16)

  315t=−173  (mod16)

  315t=11t  (mod16)

  176=−3  (mod16)

  11t=−3  (mod16)

これから

  t=9  (mod16)

がみつかる.

 t=16u+9をz=315t+206に代入すると

  z=5040u+3041

が得られる.→(その3)と一致.

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