III順天堂大学 2019年 数学 第III問解答・解説

順天堂大学 2019 問III（独立A）

(1) 1050 と 819 の最大公約数

ユークリッドの互除法を行う。 $$\begin{aligned} 1050&=1\cdot819+231,\\ 819&=3\cdot231+126,\\ 231&=1\cdot126+105,\\ 126&=1\cdot105+21,\\ 105&=5\cdot21+0. \end{aligned}$$ 最後の0でない余りは21なので、最大公約数は $$\gcd(1050,819)=21.$$

(2) 公約数は余りを割り切る

$b$ を $a$ で割った商を整数 $q$ とすれば、割り算の定理により $$b=qa+r,\qquad 0<r<a$$ である。$c$ が $a,b$ の公約数なら $a=cu,\ b=cv$ と書ける整数 $u,v$ が存在する。よって $$r=b-qa=cv-qcu=c(v-qu)$$ であり、$v-qu$ は整数だから $c\mid r$。したがって $c$ は $r$ の約数である。

(3) 最大公約数は $a,b$ の整数係数一次結合

$r_0=b,\ r_1=a$ とし、ユークリッドの互除法を続ける。各段階で $$r_{k-1}=q_k r_k+r_{k+1}$$ と書ける。余りは正の整数の範囲で次第に小さくなるため、ある段階で余りが0となる。最後の0でない余りを $r_n$ とする。

各段階で、$r_{k-1},r_k$ がともに $a,b$ の整数係数一次結合なら、 $$r_{k+1}=r_{k-1}-q_k r_k$$ も $a,b$ の整数係数一次結合である。最初の $r_0=b,\ r_1=a$ はその形なので、順にすべての余りがその形で表される。特に $$r_n=s a+t b$$ となる整数 $s,t$ がある。

最後の0でない余りは $a,b$ の最大公約数であることも確認する。割り算の式 $r_{k-1}=q_k r_k+r_{k+1}$ から、$r_{k-1},r_k$ の公約数は $r_k,r_{k+1}$ の公約数と同じである。これを繰り返すと $a,b$ の公約数全体は最後の組 $r_n,0$ の公約数全体と一致し、その最大の正の公約数は $r_n$。ゆえに $r_n=m$ であり、 $$m=s a+t b$$ と表される。

最終解答

1) $\gcd(1050,819)=21$。

2) $b=qa+r$ と書けば、公約数 $c\mid a,b$ について $r=b-qa$ も $c$ の倍数であり、$c\mid r$。

3) ユークリッドの互除法で作る最後の0でない余り $m$ は、各余りが前の2つの整数係数一次結合として保たれるため、ある整数 $s,t$ によって $m=sa+tb$ と表される。

方法

ユークリッドの互除法、整数の割り算の定理、余りの漸化的な表示を用いた。

issues

なし。