有名問題・定理から学ぶ数学

Well-Known Problems and Theorems in Mathematics

数式を枠からはみ出さずに表示するためには, 画面を横に傾けてください.

ユークリッドの互除法

ユークリッドの互除法

定理《ユークリッドの互除法》

 整数 $a$ を $0$ でない整数 $b$ で割った余りが $r$ であるとき, $a,$ $b$ の最大公約数は $b,$ $r$ の最大公約数に等しい.

証明

 除法の定理により
$a = bq+r$ ($q$: 整数)
と表せる. $a,$ $b$ の最大公約数を $g$ とおき, $b,$ $r$ の最大公約数を $h$ とおく.
(i)
$g$ は $b,$ $r = a-bq$ の公約数であるから, $h$ の最大性により, $g \leqq h$ が成り立つ.
(ii)
$h$ は $b,$ $a = bq+r$ の公約数であるから, $g$ の最大性により, $g \geqq h$ が成り立つ.
(i), (ii) から, $g = h$ である.

問題《ラメの定理》

 $a,$ $b$ を $a > b \geqq 1$ なる整数とし, 割り算 \[\begin{aligned} a &= bq_1+r_1, \quad 0 < r_1 < b, \\ b &= r_1q_2+r_2, \quad 0 < r_2 < r_1, \\ &\ \,\vdots \\ r_{l-2} &= r_{l-1}q_l+r_l, \quad 0 = r_l < r_{l-1} \end{aligned}\] により整数 $l$ と $q_1,$ $\cdots,$ $q_l,$ $r_1,$ $\cdots,$ $r_l$ を定める. また, 数列 $\{ F_n\}$ を \[ F_1 = F_2 = 1, \quad F_{n+2} = F_n+F_{n+1}\] で定め, $\alpha$ を $x^2 = x+1$ の正の解とする. 次のことを示せ.
(1)
$b \geqq F_{l+1}$ である.
(2)
$F_{n+1} \geqq \alpha ^{n-1}$ である.
(3)
$\alpha ^5 > 10$ である.
(4)
十進法で $b$ の桁数が $d$ であるとする. このとき, $a,$ $b$ の最大公約数は高々 $5d$ 回のユークリッドの互除法の計算で求まる.
発展定理$2017/09/11$$2022/04/22$

解答例

(1)
\[\begin{aligned} b &\geqq r_1+r_2, \\ &\ \,\vdots \\ r_{k-2} &\geqq r_{k-1}+r_{k} \quad (2 < k < l), \\ &\ \,\vdots \\ r_{l-2} &> r_{l-1} > r_l = 0 \end{aligned}\] が成り立つから, $r_{l-1} = 1,$ $r_{l-2} = 2,$ $\cdots,$ $r_{k-2} = r_{k-1}+r_{k},$ $\cdots,$ $b = r_1+r_2$ のとき, つまり $b = F_{l+1}$ のとき $b$ は最小になる. よって, $b \geqq F_{l+1}$ である.
(2)
$F_{n+1} \geqq \alpha ^{n-1}\ \cdots [*]$ を数学的帰納法で示す.
(i)
$n = 1,$ $2$ のとき. $F_2 = 1,$ $F_3 = 2 > \dfrac{1+\sqrt 5}{2} = \alpha$ から, $[*]$ が成り立つ.
(ii)
$n = k,$ $k+1$ ($k$: 正の整数)のとき $[*]$ が成り立つとする. このとき, $\alpha ^2 = 1+\alpha$ であるから \[\begin{aligned} F_{k+3} &= F_{k+1}+F_{k+2} \\ &\geqq \alpha ^{k-1}+\alpha ^k = \alpha ^{k-1}(1+\alpha ) \\ &= \alpha ^{k-1}\alpha ^2 = \alpha ^{k+1} \end{aligned}\] となり, $n = k+2$ のとき $[*]$ が成り立つ.
(i), (ii) から, すべての正の整数 $n$ に対して $[*]$ が成り立つ.
(3)
$\alpha = \dfrac{1+\sqrt 5}{2}$ であるから, $(1+\sqrt 5)^5 > 10\cdot 2^5 = 320$ を示せばよい. \[\begin{aligned} &(1+\sqrt 5)^5 = (1+\sqrt 5)^4(1+\sqrt 5) \\ &= \{ (1+\sqrt 5)^2\} ^2(1+\sqrt 5) = (6+2\sqrt 5)^2(1+\sqrt 5) \\ &= (56+24\sqrt 5)(1+\sqrt 5) = 176+80\sqrt 5 \end{aligned}\] であるから, $80\sqrt 5 > 144$ を示せばよい. これは $(80\sqrt 5)^2 = 32000 > 20736 = 144^2$ から従う.
(4)
$2$ つの整数 $x,$ $y$ の最大公約数を $(x,y)$ で表す. \[ (a,b) = (b,r_1) = \cdots = (r_{l-2},r_{l-1}) = (r_{l-1}q_l,r_{l-1}) = r_{l-1}\] であるから, $l \leqq 5d$ を示せばよい. $b < 10^d$ と (1), (2) と合わせると \[\alpha ^{l-1} \leqq F_{l+1} \leqq b < 10^d\] が得られる. これと (3) を合わせると \[ 10^{l-1} < \alpha ^{5(l-1)} < 10^{5d}\] となるから, $l-1 < 5d$ つまり $l < 5d+1$ であり, $l \leqq 5d$ が成り立つ.

参考

 本問で示した, 次の事実は「ラメの定理」として知られている: 正の整数 $a,$ $b\ (a > b)$ の最大公約数を求めるユークリッドの互除法の計算回数は, $b$ を十進法で表したときの桁数の $5$ 倍以下である. この定理により, $b$ が $100$ 桁の整数でも, $a,$ $b$ の最大公約数は高々 $500$ 回の計算で求まることがわかる.

問題《文字式で表された $3$ 数の最大公約数》

 $m,$ $n$ $(m > n)$ を正の整数とする. また, 整数 $a_1,$ $\cdots,$ $a_r$ の最大公約数を $(a_1,\cdots,a_r)$ で表す. $g = (m^2-n^2,2mn+n^2,m^2+mn+n^2)$ について, 次のことを示せ.
(1)
\[ g = (3mn,m(m-n),n(m-n))\] が成り立つ.
(2)
$m,$ $n$ が互いに素であるとする. このとき, \[ g = \begin{cases} 1 & (m \not\equiv n \pmod 3), \\ 3 & (m \equiv n \pmod 3) \end{cases}\] である.
(類題: $2022$ 京都大, $2022$ 東京工業大)
実戦定理$2022/07/18$$2022/07/20$

解答例

 $3$ 数の最大公約数は $2$ 数の最大公約数と残りの数の最大公約数に等しいことに注意する.
(1)
ユークリッドの互除法により, \[\begin{aligned} g &= (m^2-n^2,2mn+n^2,m^2+mn+n^2) \\ &= (m^2-n^2,2mn+n^2,m^2-mn) \\ &= (mn-n^2,2mn+n^2,m^2-mn) \\ &= (mn-n^2,3mn,m^2-mn) \\ &= (3mn,m(m-n),n(m-n)) \end{aligned}\] が成り立つ.
(2)
仮定から, $m,$ $n,$ $m-n$ のどの $2$ つも互いに素である.
(i)
$m \not\equiv n \pmod 3$ のとき. (1) と仮定から, \[ g = (3mn,m-n) = 1\] である.
(ii)
$m \equiv n \pmod 3$ のとき. (1) から, $g$ は $3mn$ の約数である. よって, $g$ の素因数 $p$ は, $3,$ または $m$ の素因数, または $n$ の素因数である.
  • $p$ が $m$ の素因数であるとき. $p$ は $n(m-n)$ の素因数, よって $m-n$ の素因数になり, $p$ は $n$ の素因数になって, 矛盾が生じる.
  • $p$ が $n$ の素因数であるとき. 同様に矛盾が生じる.
ゆえに, $p = 3$ であり, $3$ は $m$ の素因数でも $n$ の素因数でもないから(上記の議論を $p = 3$ に適用するとわかる), \[ g = 3\] である.

参考

 本問の結果は,「アイゼンシュタインの $3$ つ組」の公式の証明(こちらを参照)に使われる.