ユークリッドの互除法が成り立つ仕組みを帰納法で示す(東京都立大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$

これを文字に置きかえます。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$ が最大公約数です。

こうして，ユークリッドの互除法から言えば $\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}$

となります。

よって

$\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)に入ります。

$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_{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$ が存在する。（証明終わり）