| 最大公約数の求め方、ユークリッドの互助法の解説と応用問題 |
| ユークリッドの互助法を使えば最大公約数が求まります。 aとb(a＞b)の最大公約数を求めるにはまず aをbで割ります。 その商をq、余りをrとすると a=bq+r になります。 ここで割り算だからq＞rになっています。 今度は、bをrで割ります。 その商をp、余りをsとすると b=rp+s になります。 今度はrをsで割ります。 この操作を続けていって割り切れた時の余りが最大公約数です。 例えばrがsで割りきれるとsがaとbの最大公約数です。 ちなみに余りが1になると次の操作で1で割るから必ず割り切れます、最大公約数が1ってことでaとbは互いに素であることになります。 例えば24と78なら78を24で割って 78=24×3+6 余り6、24を6で割って 24=6×4 と割り切れます。 だから最大公約数は6です。 何故ユークリッドの互助法で最大公約数が求まるのかと言うと aとbの最大公約数をcとします。 すると a=cm b=cn でmとnは互いに素な整数と表されます。 aをbで割った商をq余りをrとすると a=bq+r ですが r=a-bq =cm-cnq =c(m-nq) でrもcの倍数です。 つまりこの操作を繰り返せば余りはどんどん小さくなっていきますがどの余りも公約数cの倍数になっていて、何回目かの余りで割り切れるとその余りは最大公約数だけになったと言うことだから、それが最大公約数になります。 これを応用すれば、大学受験でたまに出るaとbを互いに素な整数とすると mとnを整数として am+bn=1の時、mとnを全て求めよ と言うような問題が出来ます。 一般的にやるとテキストは見にくいってこともあって具体的にやります。 例えば19と71は互いに素ですが、19m+71n=1となる整数mとnを求める問題を考えます。 さっきのユークリッドの互助法の操作をしてみましょう。 71=19×3+14 19=14×1+5 14=5×2+4 5=4×1+1 余りが1になりました。 はい、ちゃんと互いに素になってますね。 これをちょっと余りだけを右辺か左辺かにします。 71-19×3=14 19-14×1=5 14-5×2=4 5-4×1=1 こう書くと、一番下の余り1は5と4で表されています。 4は下から二番目の式で5と14で表されています。 5は下から三番目の式で19と14で表されています。 14は下から四番目の式で71と19で表されています。 と言うことは、どんどん代入していくと1は71と19で表されることになります。 1=5 - 4×1 =5 - 14-5×2 =-14 - 5×3 =-14 - (19-14×1)×3 =-19×3 - 14×2 =-19×3 - (71-19×3)×3 =19×6 + 71×(-3) で1=19×6 + 71×(-3)と71と19であらわせました。 よってm=6,n=-3が一つの解答ですが、全ての解を求めるには一つの解がわかると 19m + 71n = 1…�� 19×6 + 71×(-3) = 1…�� でこれを引き算すると ��-��: 19(m-9)=71(n+3) 1が消えます。 これなら、19と71は互いに素なので n+3は19の倍数。 n+3=19k(kは整数) でこの時、代入すると m-9=71k だから n=19k-3 m=71k+9 とわかりました。 この一つの解を見つけると一般的な解がわかるようになるって言うのは大学では微分方程式とかでも使いますが高校でもたまにこの考えを用いると便利なことがあります。 例えば漸化式pn+1=qpn+r(q≠1)p1=pって問題で、pn+1とpnのとこをxとおくと x=qx+rでx=r/(1-q)ですがこれはp1=pの条件が無いとすると漸化式pn+1=qpn+rは色々な解を持ちますが全てのnでpn=xとするとx=qx+1を解いたのがxなわけだから漸化式は常になりたっていてpn=xが一つの解になっています。 これもさっきと同じように pn+1=qpn+r…�� x=qx+r…�� ��-��: pn+1-x=q(pn-x) と言うように差をとるとrが消えてpn-xは等比qの等比数列であることがわかります。 だから pn-x=(p-x)・q^(n-1) pn=x+(p-x)・q^(n-1) とわかります。 高校数学の公式や問題の解説  |
▲ページトップへ
| この記事に対するトラックバック |
| トラックバックURL
→http://kazuschool.blog94.fc2.com/tb.php/66-3432247c この記事にトラックバックする(FC2ブログユーザー) |
