ユークリッドの互除法
ユークリッドの互除法
定理《ユークリッドの互除法》
整数 $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$ が成り立つ.
問題《ラメの定理》
$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$ 回のユークリッドの互除法の計算で求まる.
(参考: $2023$ 慶應義塾大, $2018$ 東京医科歯科大)
解答例
- (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$ のとき $[*]$ が成り立つ.
- (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$ が成り立つ.
参考
- 本問で示した, 次の事実は「ラメの定理」(Lamé's theorem) として知られている: 正の整数 $a,$ $b$ $(a > b)$ の最大公約数を求めるユークリッドの互除法の計算回数は, $b$ を十進法で表したときの桁数の $5$ 倍以下である. この定理により, $b$ が $100$ 桁の整数でも, $a,$ $b$ の最大公約数は高々 $500$ 回の計算で求まることがわかる.
- 一般に, 正の整数 $a,$ $b$ $(a > b)$ の最大公約数を求めるユークリッドの互除法の計算回数は, $b$ を $n$ 進法で表したときの桁数の $\left\lceil\dfrac{1}{\log _n\alpha}\right\rceil$ 倍以下である. ここで, $\alpha = \dfrac{1+\sqrt 5}{2}$ であり, $\left\lceil\dfrac{1}{\log _n\alpha}\right\rceil$ は $\dfrac{1}{\log _n\alpha}$ 以上の最大の整数を表す.
問題《文字式で表された $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$ 東京工業大)
解答例
$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$ の素因数であるとき. 同様に矛盾が生じる.
参考
本問の結果は,「アイゼンシュタインの $3$ つ組」の公式の証明 (こちらを参照) に使われる.