すっきりだらだら

中国剰余定理を使う方法でといてみましょう。
　
何か解説みたく書いてたら講義風、というか実況中継風になっちゃった＞＜
　
例題)
47x ≡ 89 (mod 111)
答)
111=3･37であり
89 ≡ 2 (mod 3)
89 ≡ 15 (mod 37)
なので、
47x ≡ 2 (mod 3)…(1)かつ
47x ≡ 15(mod 37)…(2)　がxの満たすべき条件。
　
この2式についてそれぞれxについて解くというところまでは桜君と一緒の回答。
これについて　47x = 3y + 2　とか　47x = 37y + 15　などといった
方程式を立てて前日の解答でxを求たら確実に答は出るけど、
いちいちこれをやるのは面倒くさいからxはがんばって暗算で出します。
　
(1)についてはxが1か2に限られるのは当然だから代入すればおっけ。
(1)⇔x≡1 (mod 3)
(2)については、これは邪道だけど(←も意外と重要)、　47x = 37x + 10x　をいいことに
左辺に37を足していって10で割り切れるように、つまり一桁目を0にすればおっけーってこと。
だから15の1桁目に注目して②の両辺に37･5を足して
37x + 10 x + 37･5 ≡ 15 + 37･5 (mod 37)
ご存知のとおり37の倍数は消えてくれるから
10x ≡570 (mod 37)
10と37は互いに素だから両辺を10で割ることができて
x≡57≡20 (mod 37)
(いつもこれができるとは限りません＞＜)

つまり
　
x≡1 (mod 3)　かつ
x≡20 (mod 37)
　
がxの満たすべき条件ってこと。目立つように見やすいように余白を入れました。
　
ここからが中国剰余定理の出番。そんなに威張ることじゃないけど。
中国剰余定理の詳細は後回しにして(何)
　
37を適当に整数倍して3で割った余りが1になるようにします。
これをするには、まず最初に37を3で割って、余りが1。これは1回で成功。
つまり　37･1≡1(mod 3)･･･(3) ということ。
　
次に3を適当に整数倍して37で割った余りを20になるようにします。
これはどんどん３を足していって（つまりかける数を増やしていくってこと)
そして37で割った余りが20になるようにします。
3をどんどん足して試すのは面倒だから、20に37を足していって逆に3で割り切れりゃ同じこと。
すると20 + 1･37 = 57 = 3･19　だから
3･19≡20 (mod 37) … (4)　ということ。
　
さてここで(3)と(4)の左辺の値を足してみましょう。
37･1 + 3･19ですが･･･これは3で割ったら当然余りは1で37で割ったら当然余りは20です。
つまりこれがxなのです。
だからx≡37･1 + 3･19 = 94 *1 (mod 111)　
すなわちx≡94 (mod 111)なのです。

*1:この値がたまに111をオーバーするけどそのときはまた余りを出せばいいのです