千葉大学 融合理工学府 数学情報科学専攻 数学・情報数理学コース 2024年8月実施 専門 B10

标签：

• Euclidean-Algorithm
• Asymptotic-Upper-and-Lower-Bound-Proofs

Author

祭音Myyura (co-authored with GPT 6 Astra)

Description

整数 $a>b\ge0$ に対し、次のアルゴリズムを考える。

while b > 0:
    r := a mod b
    a := b
    b := r
return a

ループを $k$ 回実行した直後の a の値を $r_k$ とし、$r_0=a$ とする。第 $k$ 回の除算の商を $q_k$、総実行回数を $N(a,b)$ とする。

(1) $r_0,\ldots,r_N$ が単調減少することを示せ。(2) $q_k\ge1$ ($1\le k<N$)、$q_N\ge2$ を示せ。(3) $d=\gcd(a,b)$ のとき $N(a/d,b/d)=N(a,b)$ を示せ。(4) 実行回数が $O(\log b)$ であることを示せ。

题目描述

考虑 Euclid 算法，记每轮结束后的第一变量为 $r_k$、商为 $q_k$、总轮数为 $N$。(1) 证明 $r_k$ 递减。(2) 证明非末轮商至少一、末轮至少二。(3) 证明两输入同时除以最大公约数不改变轮数。(4) 证明轮数为 $O(\log b)$。

Kai

$b=0$ なら実行回数は $0$ である。以下 $b>0$ とし、$r_1=b,r_{N+1}=0$ と補って書く。

(1), (2)

各除算は

$$r_{k-1}=q_kr_k+r_{k+1},\qquad0\le r_{k+1}<r_k$$

を満たす。初めに $r_0>r_1>0$ なので $r_0>r_1>\cdots>r_N>0$。ゆえに $q_k\ge1$。最後は $r_{N-1}=q_Nr_N$ かつ $r_{N-1}>r_N$ なので $q_N\ge2$。

(3)

各剰余は $d$ の倍数である。上の等式をすべて $d$ で割ると、商 $q_k$ は変わらず、正の剰余が $0$ になる段階も変わらない。したがって $N(a/d,b/d)=N(a,b)$。

(4)

$r_{k+1}\le r_k/2$ なら次々の剰余も $r_k/2$ 以下である。$r_{k+1}>r_k/2$ の場合、$r_k$ を $r_{k+1}$ で割る商は $1$ だから

$$r_{k+2}=r_k-r_{k+1}<r_k/2.$$

従って二回ごとに剰余は少なくとも半分になる。$r_1=b$ から正の整数の剰余を保てる回数は $O(1+\log b)$ であり、$b\ge2$ では $\boxed{N(a,b)=O(\log b)}$。$b=1$ では一回で終了する。