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