■百五減算(その1)

 中国剰余定理「m1〜mkを2つずつ互いに素とする.このとき,

  x=c1  (mod m1)

  ・・・・・・・・・・・・・

  x=ck  (mod mk)

はΠmiを法として,ただひとつの解をもつ」の練習問題を掲げておく.

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

[Q]連立合同式

  x=2  (mod3)

  x=1  (mod4)

  x=3  (mod5)

を計算しよう.

x=x1+3x2+12x3とおいて,最初の式に代入する.→x1+3x2+12x3=x1=2  (mod3)→x1=2がこの合同式の解である.

→x=2+3x2+12x3を2番目の式に代入する.→2+3x2+12x3=2+3x2=1  (mod4)→3x2=−1  (mod4)→x2=1がこの合同式の解である.

→x=5+12x3を3番目の式に代入する.→5+12x3=3  (mod5)→12x3=−2  (mod5)→x3=4がこの合同式の解である.

 x=53となるので,中国剰余定理より連立合同式の解は

  x=53  (mod60)

である.

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

【1】百五減算

 上のような問題を以下のように書き換えることにする.

 p1,p2,p3が互いに素であるとき,p1で割って余りがr1,p2で割って余りがr2,p3で割って余りがr3になる自然数Aは一意に定まる.さらに,p1で割って1余る数かつp2p3の倍数をx,p2で割って1余る数かつp3p1の倍数をy,p3で割って1余る数かつp1p2の倍数をzとするとき,特殊解

  A=xr1+yr2+zr3

が得られる.

[Q]連立合同式

  x=2  (mod3)

  x=1  (mod5)

  x=5  (mod7)

を計算しよう.

 p1で割って1余る数かつp2p3の倍数をx=70

 p2で割って1余る数かつp3p1の倍数をy=21

 p3で割って1余る数かつp1p2の倍数をz=15

  A=xr1+yr2+zr3=70・2+21・1+15・5=236

  p1p2p3=105

  206−105・2=26

[Q]連立合同式

  x=2  (mod3)

  x=3  (mod5)

  x=2  (mod7)

を計算しよう.

 p1で割って1余る数かつp2p3の倍数をx=70

 p2で割って1余る数かつp3p1の倍数をy=21

 p3で割って1余る数かつp1p2の倍数をz=15

  x=2  (mod3)

  x=1  (mod4)

  x=3  (mod5)

  A=xr1+yr2+zr3=70・2+21・1+15・2=191

  p1p2p3=105

  191−105=86

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