■中国剰余定理

 新年恒例のU嬢さんからの質問である.

[Q]篭にタマゴが何個か入っている.3個ずつ取り出したら2個余り,5個ずつ取り出したら3個余り,7個ずつ取り出したら2個余った.最も小さいタマゴの数は?

 いろいろな解き方があると思われるが,

  [参]ウォルターズ「算数からはじめよう! 数論」岩波書店

に掲載されている方法を紹介したい.

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

[A]  x≡2  (mod3)

     x≡3  (mod5)

     x≡2  (mod7)

 m1=3,m2=5,m3=7

 x=x1+m1x2+m1m2x3=x1+3x2+15x3

とおいて計算する.

[1]に代入すると,x1≡2  (mod3)→x1=2とする.→x=2+3x2+15x3

[2]に代入すると,2+3x2≡3→3x2≡1  (mod5)→x2=2とする.→x=8+15x3

[3]に代入すると,8+15x3≡2→15x3≡−6  (mod7)→x3=1とする.→x=23.

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