ユークリッドの互除法が成り立つ仕組みを帰納法で示す(東京都立大2018理学部第3問)

ユークリッドの互除法の証明を帰納法でやる。教科書の説明通りのことを文字に置きかえて帰納法使ったら証明できるよっていう話。

以下の問いに答えなさい。(東京都立大2018)

(1) 正の整数 $p,q,f$ および整数 $r$ が次の関係をみたしているとする。

$p=fq+r$

ただし,$0\leqq r<q$ とする。このとき整数 $d$ が $p$ と $q$ の公約数であることと,$d$ が $q$ と $r$ の公約数であることは同値であることを示しなさい。

(2) 正の整数 $k,m$ の最大公約数を $\text{gcd}(k,m)$ で表す。$p,q$ を,$p>q$ をみたす正の整数とする。また,$n\geqq2$ とし,$2n-1$ 個の正の整数 $f_1,f_2,\cdots,f_{n-1},r_1,r_2,\cdots,r_n$ が次の関係をみたしているとする。

$p=r_1$
$q=r_2$
$r_1=f_1r_2+r_3$,$r_3<r_2$
$\vdots$
$r_{n-2}=f_{n-2}r_{n-1}+r_n$,$r_n<r_{n-1}$
$r_{n-1}=f_{n-1}r_n$

このとき,$\text{gcd}(p,q)=\text{gcd}(r_j,r_{j+1})$ $(j=1,2,\cdots,n-1)$ が成り立つことを $j$ に関する数学的帰納法で示しなさい。

(3) $p$ と $q$ を互いに素な正の整数とする。このとき,$ap+bq=1$ をみたす整数 $a,b$ が存在することを示しなさい。

公約数を示す

(1)から始めます。

まず,$p=fq+r$ って $p=$割る数×商+余り の式だってことに気づくのが大事。

整数 $d$ が $p$ と $q$ の公約数であるということは,$p$ は $d$ の倍数であり,$q$ も $d$ の倍数であるということです。

$p=dp’$,$q=dq’$

とすると
$p=fq+r$
$dp’=fdq’+r$
$r=dp’-fdq’$
$r=d(p’-fq’)$ ・・・①

右辺が $d$ の倍数であるということは左辺も $d$ の倍数でなければイコール関係は成り立ちません。よって

$r=dr’$ とすると
$p=fdq’+dr’$
$p=d(fq’+r’)$ ・・・②

①,②より,整数 $d$ が $p$ と $q$ の公約数であることと,$d$ が $q$ と $r$ の公約数であることは同値である。(証明終わり)

ユークリッドの互除法

(2)に進みます。

割る数×商+余りの式っぽいけど,何で並べてるのか。

これ,ユークリッドの互除法。

ユークリッドの互除法は,はじめ最大公約数を求める方法として学びます。

たとえば,506 と 437 の最大公約数を求めるなら

$506=\underline{437}\cdot1+\underline{69}$
$\underline{437}=69\cdot6+\underline{23}$
$\underline{69}=\underline{23}\cdot3+0$

最大公約数は $23$

最後,余りが 0 になったら終わりでしたね。

これを文字に置きかえます。507 ⇒ $r_1$,437 ⇒ $r_2$ として,さらに商を $f_1$,余りを $r_3$ とすると

$r_1=r_2f_1+r_3$
$r_2=r_3f_2+r_4$
$r_3=r_4f_3+0$

となり,問題文の式と同じになることが確認できます。そして $r4$ が最大公約数です。

この式,そういう意味なんだ。
これが分かってないと(3)が解けない。

こうして,ユークリッドの互除法から言えば $\text{gcd}(p,q)=r_n$ ということになります。

式の意味が分かったところで,あとは数学的帰納法で最大公約数についての証明を書いていきましょう。

$\text{gcd}(p,q)=\text{gcd}(r_j,r_{j+1})$ $(j=1,2,\cdots,n-1)$ ・・・(*)

として

[I] $j=1$ のとき

$p=r_1$,$q=r_2$ より

$\text{gcd}(p,q)=\text{gcd}(r_1,r_2)=r_n$

よって,$j=1$ のとき(*)は成り立つ。

[II] $j=k$ として(*)が成り立つと仮定すると,$j=k+1$ のとき

問題文の式を $k$ を用いて表すとこのようになります。

$r_k=f_kr_{k+1}+r_{k+2}$

$k$ を $j$ に置きかえると

$r_j=f_kr_{j+1}+r_{j+2}$

この式から,$\text{gcd}(r_j,r_{k+j})=\text{gcd}(r_{k+j},r_{k+j})$ が成り立ちます。

さらに,式を進めていくと

$r_j=f_jr_{j+1}+r_{j+2}$
$r_{j+1}=f_jr_{j+2}+r_{j+3}$
$\vdots$
$r_{n-1}=f_{n-1}{r_n}$

となります。

結局,式を $j=k$ から始めようが,$k+1$ から始めようが行きつくところは同じってこと。

よって

$\text{gcd}(p,q)=\text{gcd}(r_k,r_{k+1})=\text{gcd}(r_{k+1},r_{k+2})=r_n$

$\text{gcd}(r_{k+1},r_{k+2})=r_n$ であるから,$j=k+1$ において,(*)が成り立つ。

[I],[II]より,$j=1,2,\cdots,n-1$ について,$\text{gcd}(p,q)=\text{gcd}(r_j,r_{j+1})$ が成り立つ。(証明終わり)

ユークリッドの互除法が成り立つ仕組み

(3)に入ります。

これも,$19x+11y=1$ の整数解を求めよ,みたいな問題で見たことあるよね。
解の一つを見つけるヤツか。
解の一つを見つけるときに,ユークリッドの互除法を使うと良かった。
$p$ を 19,$q$ を 11 として,$x,y$ を $a,b$ に置きかえると $ap+bq=1$ となる。つまり,整数 $a,b$ が存在するってのは,ユークリッドの互除法使って解の一つとなる整数を示すってこと。

$a_jr_j+b_jr_{j+1}=1$ ・・・(*)

として,(2)の関係を満たすとする。

[I] $j=1$ のとき

$p=r_1$
$q=r_2$
$r_1=f_1r_2+r_3$,$r_3<r_2$
$\vdots$
$r_{n-2}=f_{n-2}r_{n-1}+r_n$,$r_n<r_{n-1}$ ・・・③
$r_{n-1}=f_{n-1}r_n$

(2)でやったように,$r_n$ が最大公約数だった。

$p$ と $q$ は互いに素だから,$\text{gcd}(p,q)=1$。つまり $r_n=1$

③を移項すると

$r_{n-2}-f_{n-2}r_{n-1}=r_n$
$r_{n-2}-f_{n-2}r_{n-1}=1$

これを $1\cdot r_{n-2}+(-f_{n-2})r_{n-1}=1$ と考えると,$a=1$,$b=-f_{n-2}$ と見なすことができます。今回は文字に入る値はすべて整数だから,$f_{n-2}$ も何らかの整数です。

よって,(*)をみたす整数 $a_j$,$b_j$ が存在する。

[II] $j=k$ として(*)が成り立つと仮定すると,$j=k+1$ のとき

$a_{k+1}r_{k+1}+b_{k+1}r_{k+2}=1$ ・・・④

また,(2)より
$r_k=f_kr_{k+1}+r_{k+2}$

が成り立つことを利用する。これを移項して

$r_k-f_kr_{k+1}=r_{k+2}$

④に代入して

$a_{k+1}r_{k+1}+b_{k+1}(r_k-f_kr_{k+1})=1$

式を整理して

$a_{k+1}r_{k+1}+b_{k+1}r_k-b_{k+1}f_kr_{k+1}=1$
$b_{k+1}r_k+(-a_{k+1}b_{k+1}f_k)r_{k+1}=1$ ・・・⑤

$b_{k+1}$ と $-a_{k+1}b_{k+1}f_k$ は何らかの整数であることは間違いないので,それぞれ $a$,$b$ に置きかえることができます。

勝手に置きかえていいの?
話の最初に戻って。$a$,$b$ ってのは結局,互除法使って求める解の一つだから。ここでは,その値自体を求めるんじゃなくて,その値が整数であることだけ示せればオッケーなの。実際の値が何だろうと,解の一つが見つかればそれを $a$ と $b$ にしようねってこと。
そうなの?
そうなの。こういうの,やってるうちに何やりたいのか分からなくなるから,ちゃんと問題文で聞かれてること確認して。

$a_{k+1}=b_{k+1}$,$b_{k+1}=-a_{k+1}b_{k+1}f_k$ とすると,⑤は

$a_{k+1}r_{k+1}+b_{k+1}r_{k+2}=1$

となるので,$j=k+1$ のときも(*)に当てはまる $a_j$ と $b_j$ が存在する。

[I],[II]より,$ap+bq=1$ をみたす整数 $a$,$b$ が存在する。(証明終わり)