ユークリッドの互除法、既約分数であることの証明

互除法の原理$   $自然数aを自然数bで割ったときの商をq,\ 余りをrとする.   $ここで,\ g₁はbの約数でもあるから,\ g₁はbとrの公約数}である.$   $よって,\ g₂がbとrの最大公約数であることから g₂ g₁   $a}=qb+r=q g₂b”+g₂r’=g₂}(qb”+r’)\ より,\ g₂はaの約数である.$   $ここで,\ g₂はbの約数でもあるから,\ g₂はaとbの公約数}である.$   $よって,\ g₁がaとbの最大公約数であることから g₁ g₂} 整数a,\ bの最大公約数(greatest\ common divisor})を\ \gcd(a,\ b)\ と表すことにする. 整数の除法について成り立つ等式a=bq+rにおいて,\ 次が成立する. {「割られる数aと割る数bの最大公約数」=「割る数bと余りrの最大公約数」} 証明も重要だが,\ 高校生は使う機会が少ない論法であり,\ 中々難しい. {「p q\ かつ\ q p」\ を示すことで,\ p=qを示す}という論法である. 記述を簡単にするため,\ 最大公約数を文字で設定する. 日本語「a,\ bの最大公約数がg」は,\ 数式「a=ga’,\ b=gb’」に変換できる. a’,\ b’は互いに素な整数だが,\ この証明では不要なので省略した. {既存の文字a,\ bを消去し,\ 共通因数g₁をもつものをまとめる.} ここから,\ g₁がbとrの公約数であることがわかる. 一方,\ \gcd(b,\ r)=g₂\ であったから,\ g₂ g₁\ となるわけである. g₁ g₂\ も同様にして示される. ユークリッドの互除法}(2つの自然数の最大公約数の求め方)}   互除法の原理を余りが0になるまで繰り返し用いる.   $270と396の最大公約数を互除法で求める.$ 通常,\ 最大公約数は素因数分解して求める. しかし,\ 巨大な数や素数の場合,\ 素因数分解が容易ではない. 互除法は,\ 必ず最大公約数を求めることができる万能な方法である. とする.\ 自然数aを自然数bで割ると,\ 必ず{余りrはbより小さい数}になる. よって,\ 必ず\gcd(a,\ b)=\gcd(b,\ r)は,\ 左辺より右辺の値が小さくなる. これを繰り返してどんどん小さい値にしていけば,\ 最大公約数が求まるのである. 39270\ より,\ 396を270で割ると 396270=1126 除法に関する等式で表したものを左,\ 最大公約数の記号を用いたものを右に示した. これを繰り返し,\ {余りが0になったときの商が最大公約数}である. 結局,\ 270と396の最大公約数は,\ 126と18の最大公約数に帰着する. 除法は筆算のほうがわかりやすいという人も多いだろう. 上に示したように,\ {余りを左に書いて,\ 右から左へ計算を進めていく.} nを自然数とするとき,\ n³+n²+3とn²-1の最大公約数として考えら$ $れる数をすべて求めよ.$  $ここで 15の正の約数は  文字式も除法によってA=BQ+Rの形にすることで,\ 互除法が適用できる. 筆算で割ればよいが,\ その過程は省略し,\ 結果だけを示した. 余りの次数は,\ 必ず割る式の次数よりも低くなる. {余りが定数になるまで繰り返たとき,\ 定数の約数が最大公約数の候補になる.} n=1のとき最大公約数5, n=11のとき最大公約数15となる. a,\ bを互いに素な自然数とする $このとき,\ {4a+9b}{3a+7b}が既約分数であることを示せ.$ {4a+9bと3a+7bは互いに素}であるから,\ {既約分数である.}$} 互除法の原理は,\ A=BQ+Rの形で表された式に対して一般的に成立する. つまり,\ 割り算は重要ではなく,\ {A=BQ+Rの形にすること自体が重要}である. 互除法の原理を使うには,\ \gcd(A,\ B)よりも\gcd(B,\ R)が簡単になる必要がある. 本問では,\ {係数を小さくする方向で式変形}すると,\ \gcd(B,\ R)が簡単になる. 最後,\ {a+2bを2 b+aとみる}ことができれば,\ \gcd(b,\ a)に帰着する. a,\ bは互いに素から,\ \gcd(a,\ b)=1\ であり,\ 4a+9bと3a+7bが互いに素となる.

タイトルとURLをコピーしました