2006年2月7日火曜日

不定方程式

ある高校の特色入試
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 は合同計算の上に成り立つ理論で作られている.>サルにもわかるRSA暗号

0 件のコメント:

コメントを投稿

「コメントの記入者:」は「匿名」ではなく,「名前/URL」を選んで,なにかニックネームを入れてください.URL は空欄で構いません.