■中国剰余定理(その4)

[Q]あるクラスでバスケットのチーム編成をしたら2人,野球では1人,サッカーでは4人余った.このクラスの人数は?

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

[A]連立合同方程式

     x≡2  (mod5)

     x≡1  (mod9)

     x≡4  (mod11)

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

 m1=5,m2=9,m3=11

 x=x1+m1x2+m1m2x3=x1+5x2+45x3

とおいて計算する.

[1]に代入すると,x1≡2  (mod5)→x1=2とする.→x=2+5x2+45x3

[2]に代入すると,2+5x2≡1→5x2≡−1  (mod9)→x2=7とする.→x=37+45x3

[3]に代入すると,37+45x3≡4→45x3≡0  (mod11)→x3=0とする.→x=37.

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

[1]0〜54の整数を5で割ったときの剰余を示す

   0  1  2  3  4  5  6  7  8  9

0: 0  1  2  3  4  0  1  2  3  4

1: 0  1  2  3  4  0  1  2  3  4

2: 0  1  2  3  4  0  1  2  3  4

3: 0  1  2  3  4  0  1  2  3  4

4: 0  1  2  3  4  0  1  2  3  4

5: 0  1  2  3  4

[2]0〜54の整数を11で割ったときの剰余を示す

   0  1  2  3  4  5  6  7  8  9

0: 0  1  2  3  4  5  6  7  8  9

1:10  0  1  2  3  4  5  6  7  8

2: 9 10  0  1  2  3  4  5  6  7

3: 8  9 10  0  1  2  3  4  5  6

4: 7  8  9 10  0  1  2  3  4  5

5: 6  7  8  9 10

[3]0〜54の整数を5で割ったときの剰余をa,11で割ったときの剰余をbとする.

a\b0  1  2  3  4  5  6  7  8  9  10

0: 0 45 35 25 15  5 50 40 30 20  10

1:11  1 46 36 26 16  6 51 41 31  21

2:22 12  2 47 37 27 17  7 52 42  32

3:33 23 13  3 48 38 28 18  8 53  43

4:44 34 24 14  4 49 39 29 19  9  54

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

 上の表[3]は

     x≡2  (mod5)

     x≡4  (mod11)

の解が37であることを示しているが,0〜54の整数がすべて現れていることに注意.これは5と11が互いに素であることによる.

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