自然数aを自然数bで割ったときの商をq,\ 余りをrとする.$
整数a,\ bの最大公約数(greatest\ common divisor})を\ g(a,\ b)\ と表すことにする.
単に(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_1\,をもつものをまとめ,\ 倍数・約数条件を考慮する.}
すると,\ g_2≧ g_1\,を示すことができる.\ \ g_1≧ g_2\,の証明も同様である.
一般的な証明1に加え,\ 高校生にとってより自然に感じるであろう証明2も示した.
b=g_1･○,\ r=g_1･□\ \ (\,○と□は互いに素)}と表せることを示せば,\ g(b,\ r)=g_1\,が示される.
b,\ rがg_1\,をくくり出せることと,\ ○と□が互いに素であることを二段階で示す.}
互いに素の証明は,\ 素数の公約数をもつと仮定して矛盾を導く}のであった(背理法}).
整数の除法の原理は,\ 「\,a=qb+r\ (0≦ rbとする.\ 自然数aを自然数bで割ると,\ 必ず余りrはbより小さい数}になる.
よって,\ g(a,\ b)=g(b,\ r)を適用すると,\ 必ず左辺より右辺の値が小さくなる.
これを繰り返し適用して値を小さくしていけば,\ いつかは確実に最大公約数が求まる}わけである.
396>270\ より,\ 396を270で割ると 396÷270=1･･･126
等式で表したものを左,\ \gcd を用いて表したものを右に示したので,\ 対応を確認してほしい.
割り算を繰り返し,\ 余りが0になったときの割る数が最大公約数}である.
270と396の最大公約数を求めることは,\ 126と18の最大公約数を求めることに等しいわけである.
単に2つの具体的な整数の最大公約数を求めるだけならば,\ 筆算表記が便利である.
余りを左に書いて割ることを繰り返せばよい.}
試験では,\ 多くても5回程度の割り算で最大公約数が求まるように問題が作られているはずである.
それだけ繰り返しても最大公約数が見つからない(割り切れない)場合,\ 計算ミスを疑った方がよい.
nを自然数とする.\ \ 2数4n+10と3n+5について,\ 以下の問いに答えよ.$
(1)\ \ 2数の最大公約数が5となるような50以下の自然数$n$をすべて求めよ.
(2)\ \ 2数の最大公約数として考えられる数をすべて求めよ. \\
$n=20}\,のとき$ & $4n+10=18,\ 3n+5=11より$ & $最大公約数1$
$n=10}\,のとき$ & $4n+10=14,\ 3n+5=80}\,より$ & $最大公約数2$
$n=10のとき$ & $4n+10=50,\ 3n+5=35より$ & $最大公約数5$
$n=50}\,のとき$ & $4n+10=30,\ 3n+5=20より$ & $最大公約数10$
見かけ上文字式であっても,\ A=BQ+Rの形さえ作り出せば,\ 互除法の原理を適用できる.}
ただし,\ g(A,\ B)よりもg(B,\ R)が簡単にならなければ適用する意味がない.
文字式の場合,\ Rの次数が低く,\ 係数が小さくなるようにA=BQ+Rの形を作る}ことを目指す.
結局,\,4n+10と3n+5の最大公約数を考えることは,\,n+5と10の最大公約数を考えることである.
(1)\ \ 互除法の原理によって2数のうち一方が定数になっていれば,\ 後は話が早い.
\ \ 定数の約数が最大公約数の候補}である.
\ \ 10=2･5より,\ 最大公約数になる可能性がある数は,\ 1,\ 2,\ 5,\ 10に限られる.
\ \ よって,\ 最大公約数が5となるための条件は,\ n+5が5の倍数だが2の倍数でないことである.
\ \ 言い換えると,\ n+5が5の倍数だが10の倍数でないことである.
\ \ n+5の範囲に注意してすべて書き出せばよい.
(2)\ \ 可能性がある1,\ 2,\ 5,\ 10が実際にありえるかを確認する.\ 一例を挙げておけば十分である.
\ \ 最大公約数が1となるのは,\ n+5が2の倍数でも5の倍数でもないときである. \rei\ \ n+5=7
\ \ 最大公約数が2となるのは,\ n+5が2の倍数だが5の倍数でないときである. \rei\ \ n+5=6
\ \ 最大公約数が10となるのは,\ n+5が2の倍数かつ5の倍数のときである. \rei\ \ n+5=10
a,\ bを互いに素な自然数とする.$
このとき,\ $4a+9b}{3a+7b}$が既約分数であることを示せ. \\
4a+9bと3a+7bは最大公約数が1}であるから,\ 既約分数である.}$} \\
$4a+9bと3a+7bが素数pを公約数にもつと仮定}する.$
このとき,\ $4a+9b=pk,\ \ 3a+7b=pl\ (k,\ l:整数)$とおける.
$a=p(7k-9l),\ \ b=p(4l-3k)$より,\ $a,\ b$はともに$p$の倍数である.
これは,\ $a,\ b$が互いに素であることと矛盾}する.
∴ 4a+9bと3a+7bは互いに素}であるから,\ 既約分数である.}$}
既約分数ということは,\ 「分子と分母の最大公約数が1\,」「分子と分母が互いに素」}ということである.
最大公約数を考えるのであれば,\ ユークリッドの互除法が有効である.
文字が複数ある場合でも,\ A=BQ+Rの形を作ると互除法の原理を適用できる.
本問の場合,\ Rの係数が小さくなるように変形}していくとよい.
結局,\ 4a+9b,\ 3a+7bの最大公約数を考えることは,\ a,\ bの最大公約数を考えることである.
a,\ bは互いに素,\ つまりg(a,\ b)=1であるから,\ g(4a+9b,\ 3a+7b)=1が示される.
整数分野を順当に学習してきたならば,\ 互いに素を背理法}で証明する別解の方が自然かもしれない.
素数の公約数をもつと仮定して矛盾を導く}のであった.
