受験数学わんこらスクール
京大理学部で数学をやったわんこらが中学生や高校生、受験生に数学の公式や問題を解説します。

最大公約数の求め方、ユークリッドの互除法の解説と応用問題
ユークリッドの互除法を使えば最大公約数が求まります。

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×4

=19×3 - (71-19×3)×4

=19×15 - 71×4

で1=19×15 + 71×(-4)と71と19であらわせました。

よってm=15,n=-4が一つの解答ですが、全ての解を求めるには一つの解がわかると

19m + 71n = 1…①
19×15 + 71×(-4) = 1…②

でこれを引き算すると
①-②:
19(m-15)=71(n+4)
1が消えます。

これなら、19と71は互いに素なので
n+4は19の倍数。

n+4=19k(kは整数)

でこの時、代入すると

m-15=71k

だから
n=19k-4
m=71k+15
とわかりました。


この一つの解を見つけると一般的な解がわかるようになるって言うのは大学では微分方程式とかでも使いますが高校でもたまにこの考えを用いると便利なことがあります。

例えば漸化式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ブログユーザー)
▲ページトップへ
プロフィール

わんこら

Author:わんこら
京都大学理学部で数学と物理を勉強し、数学を専攻しました。
東京で数学と物理の講師やってます

わんこら日記で日記とか勉強の仕方とか書いています

わんこら式数学の勉強法

メール
迷惑メールにされる危険性があるので出来るだけ
kazuyuki_ht○guitar.ocn.ne.jp
(○を@にしてください)に送ってください
勉強とかでどんな悩み持ってるかなど色々と教えてくれると嬉しいです。
わんこら式のやり方についてのメールはわんこら式診断プログラムを参考にしてください

詳しいプロフィール

人気blogランキングへ



にほんブログ村 受験ブログへ



学生広場

相互リンクも募集してます。

何かあれば
kazuschool_ht★yahoo.co.jp
かメールフォームからメールください。
(★を@にしてください)

カテゴリー

メールフォーム

名前:
メール:
件名:
本文:

FC2カウンター

リンク

このブログをリンクに追加する

お勧めの参考書、ノート

数学でお勧めのノートは
KOKUYOの無地
理由




センター試験は過去問が大切


チャートが終わったらお勧め
大学への数学1対1シリーズ
数学1


数学A


数学2


数学B


数学3


数学C

月別アーカイブ

ブログ内検索

RSSフィード

最近のトラックバック

ブロとも申請フォーム

この人とブロともになる

  1. 無料アクセス解析