不定方程式

ある高校の特色入試

150円のりんごと140円のみかんを、合わせて2620円分買いました。
何個ずつ買ったでしょう。

式：150x＋140y＝2620

中学生が解くなら，x, y に適当に入れて合わせるので十分だろう．
試行錯誤でできる．
「特色ある入学者選抜」なら，その過程を作文すればいい．

数字がでかいとめんどうだから両辺を10で割るのがスタート．

式：15x＋14y＝262

14y=262-15x に代入していく．
x=1 なら，15・1=15
14y=262-15=247=13・19 は14で割れない．
x=2 なら，15・2=30
14y=262-30=232=2^3・29 は14で割れない．
x=3 なら，15・3=45
14y=262-45=217=7・39 は14で割れない．
x=4 なら，15・4=60
14y=262-50=202=2・101 は14で割れない．
x=5 なら，15・5=75
14y=262-75=187=11・17 は14で割れない．
x=6 なら，15・6=90
14y=262-90=172=2・43 は14で割れない．
x=7 なら，15・6=105
14y=262-105=157 は14で割れない．
x=8 なら，15・8=120
14y=262-120=142=2・71 は14で割れない．
x=9 なら，15・9=135
14y=262-135=127 は14で割れない．
x=10 なら，15・10=150
14y=262-150=112=2^4・7 は14で割れるので命中．他にないかな．
x=11 なら，15・11=165
14y=262-165=97 は14で割れない．
x=12 なら，15・12=180
14y=262-180=82=2・41 は14で割れない．
x=13 なら，15・13=195
14y=262-195=67 は14で割れない．
x=14 なら，15・14=210
14y=262-210=52=2^2・13 は14で割れない．
x=15 なら，15・15=225
14y=262-225=37 は14で割れない．
x=16 なら，15・16=240
14y=262-240=22=2・11 は14で割れない．
x=17 なら，15・17=255
14y=262-255=7 は14で割れない．
これ以上はyが負になるのでだめ．
つまり x=10のときy=112÷14=8

大学入試などで高校生が解くなら，もう少し組織的に解くべきかな．
両辺を10で割って
　15x+14y=262
　14y=262-15x
左辺は2の倍数なので，15xは2の倍数．
15と2は互いに素なので，xが2の倍数より，x=2t とする．
　14y=262-15(2t)
　7y=131-15t
・・・うーん，この問題の場合ちょっと無理かな．この方針で131が7の倍数にでもなれば，簡単に求められるというパターンを大学の入試問題ではよく見る．131は素数なのでこの解き方はこれでお手上げ．
じゃあ伝家の宝刀を抜くか．

伝家の宝刀，合同式を使った不定方程式の解法

　15x+14y=262
　15x=-14y+262≡10 (mod 14)
　15x≡x (mod14)　より x≡10 (mod 14)
ゆえに x=10+14t である．
　15(10+14t)+14y=262，14y=112-14×15t，
　y=8-15t
y>0 より t=0 で y=8，x=10

とあっさりだが，知識がなければ絶対無理．逆に知識さえあれば，鼻歌まじりだな．
教科書には載っていないが，受験補習をするなら，真っ先に扱いたい題材ではある．

合同式とは「14を法とする」のとき「mod 14」と付記して，「14で割った余りが等しければ合同≡」という式．
たとえば，33÷14=2余り5 で，5÷14=0余り5 より
　33≡5 (mod 14)
などと書き，「33と5は14を法として合同」という．

言い換えると，33-5=28 は14で割り切れるから33と5は合同といえるので，
　2数の差が14で割り切れるとき，2数は「14を法として合同」という．
と定義する場合もある．

上記の解法では，合同式の変形を断りなしにたくさん使っている．
　-14y+262≡10　(mod 14)
の根拠は-14yはそもそも14の倍数なので14で割った余りは0だから（または-14y=-14(y-0)だから0との差が14の倍数）
　-14y≡0 (mod 0)
といえる．したがって
　-14y+262≡0+262=262 (mod 14)
さらに，262÷14=18余り10だから（または262-10=252=14・18で262と10の差が14の倍数）
　262≡10 (mod 14)．
ということで，
　-14y+262≡10　(mod 14)
となる．

　15x≡x　(mod 14)
の根拠は　15x=14x+x で14xが14の倍数で0と合同となるから（または15x-x=14xだから15xとxとの差が14の倍数），
　15x=14x+x≡0+x=x　(mod 14)

合同式はそれはそれで一つの「体系」だから身につくとこれほど便利なものはない．
慣れると，こんな計算もできる．
問　2006^100 を7で割った余りは？
解
2006≡4 (mod 7)
4^2=16≡2 (mod 7)
4^3=4^2・4≡2・4=8≡1 (mod 7)
2006^100≡4^100=4^99・4=(4^3)^33・4≡1^33・4=1・4=4 (mod 7)
答 4

インターネットの暗号技術RSA は合同計算の上に成り立つ理論で作られている．＞サルにもわかるＲＳＡ暗号