$$\newcommand{AA}[0]{\mathscr{A}} \newcommand{abs}[1]{\left\lvert#1\right\rvert} \newcommand{BB}[0]{\mathscr{B}} \newcommand{bbe}[0]{\mathbb{e}} \newcommand{Bu}[0]{\mathbf{u}} \newcommand{Bv}[0]{\mathbf{v}} \newcommand{C}[0]{\mathbb{C}} \newcommand{CC}[0]{\mathscr{C}} \newcommand{F}[0]{\mathbb{F}} \newcommand{floor}[1]{\left\lfloor#1\right\rfloor} \newcommand{ind}[0]{\operatorname{ind}} \newcommand{K}[0]{\mathbb{K}} \newcommand{LCM}[0]{\mathrm{LCM}} \newcommand{Mod}[1]{\ \left(\mathrm{mod}\ #1\right)} \newcommand{N}[0]{\mathbb{N}} \newcommand{nequiv}[0]{\not\equiv} \newcommand{ord}[0]{\operatorname{Ord}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$


与えられた$2$つの数の最大公約数を実際に求めるには、Euclidの互除法という高速な計算方法がある。 前ページの命題1 より与えられた$2$つの数の最小公倍数は最大公約数を用いてあらわすことができるから、与えられた$2$つの数の最小公倍数を求める実用的な計算方法も得られたことになる。


与えられた2つの整数 $a\geq b>0$ について $a_0=a, a_1=b$ とし
$$\begin{split} a_0= & q_1 a_1+a_2 (0\leq a_2< a_1), \\ a_1= & q_2 a_2+a_3 (0\leq a_3< a_2), \\ \ldots \\ a_{k-1}= & q_k a_k+a_{k+1} (0\leq a_{k+1}< a_k), \\ \ldots \end{split}$$
となる整数 $q_1, a_2, q_2, a_3, \ldots$$a_{s+1}=0$ となるまで繰り返しとっていくと、$a_{s-1}=q_s a_s$, $a_{s+1}=0$ となる $s$ が必ず存在する、さらにその場合 $a_s=\gcd(a, b)$ となる。

$a_{n+1}=0$ となる $n$ が存在しないと仮定すると
$$b=a_1>a_2>\cdots \geq 0$$
より、$0\leq a_{b+2}\leq b+1-(b+2)<0$ となり、矛盾するから、$a_{n+1}=0$ となる $n$ は必ず存在する。

そこでそのような最小の $n$$s$ とおくと $a_{s-1}=q_s a_s$ より $a_s\mid a_{s-1}$ となる。
$1\leq k\leq s$ かつ $a_s\mid a_k, a_{k+1}, \ldots, a_s$ とすると $a_{k-1}=q_k a_k+a_{k+1}$$a_s$ の倍数だから数学的帰納法より $a=a_0, b=a_1, \ldots, a_s$ はすべて $a_s$ の倍数となる。とくに $a_s$$a, b$ の公約数である。

一方、$a_0=a, a_1=b$$\gcd(a_0, a_1)=\gcd(a, b)$ で割り切れる。
$a_0, a_1, \ldots, a_k$$\gcd(a, b)$ で割り切れるとき
$a_{k+1}=a_{k-1}-q_k a_k$$\gcd(a, b)$ で割り切れる。
よって 数学的帰納法より $a=a_0, b=a_1, \ldots, a_s$ はすべて $\gcd(a, b)$ の倍数となる。とくに $a_s$$\gcd(a, b)$ の倍数である。

以上のことより $a_s=\gcd(a, b)$ となる。


Euclidの互除法にあらわれる各 $a_i (0\leq i\leq s)$$m_i a+n_i b (m_i, n_i\in\Z)$ の形にあらわすことができる。さらに $m_k, n_k$$q_1, q_2, \ldots, q_{k-1}$ から計算できる。実際 $a_0=a, a_1=b$ で、かつ $a_0, a_1, \ldots, a_k$$m_i a+n_i b (m_i, n_i\in\Z)$ の形にあらわすことができたとき
$$a_{k+1}=a_{k-1}-q_k a_k=(m_{k-1} a+n_{k-1} b)-q_k(m_k a+n_k b)=(m_{k-1}-q_k m_k) a+(n_{k-1}-q_k n_k)b$$
となる。とくに $\gcd(a, b)=ma+nb$ となる整数 $m, n$ がとれる。



$a_1, a_2, \ldots, a_k$ を任意の $k$ 個の整数 とする。このとき
$$a_1 x_1+a_2 x_2+\cdots +a_k x_k=n$$
となる整数 $x_1, x_2, \ldots, x_k$ が存在する $\Longleftrightarrow \gcd(a_1, a_2, \ldots, a_k)\mid n$.

$d=\gcd(a_1, a_2, \ldots, a_k), a_i=d b_i$ とおく。
$$a_1 x_1+a_2 x_2+\cdots +a_k x_k=n$$
となる整数 $x_1, x_2, \ldots, x_k$ が存在するとき、
$$n=d(b_1 x_1+b_2 x_2+\cdots +b_k x_k)$$
より $n$$d=\gcd(a_1, a_2, \ldots, a_k)$ の倍数である。

$$a_1 x_1+a_2 x_2+\cdots +a_k x_k=m, a_1 y_1+a_2 y_2+\cdots +a_k y_k=n$$
となる整数 $x_1, x_2, \ldots, x_k, y_1, y_2, \ldots, y_k$ が存在するとき、任意の整数 $s, t$ について
$$a_1 (sx_1+ty_1)+a_2 (sx_2+ty_2)+\cdots +a_k (sx_k+ty_k)=sm+tn$$
$$a_1 z_1+a_2 z_2+\cdots a_k z_k=sm+tn$$
となる $z_1, z_2, \ldots, z_k$ がとれる。よって 倍数と約数:定理4 より
$$a_1 x_1+a_2 x_2+\cdots +a_k x_k=n$$
となる整数 $x_1, x_2, \ldots, x_k$ が存在するような最小の正の $n$$n_0$ とおくと
$$\exists x_1, x_2, \ldots, x_k \in \Z [a_1 x_1+a_2 x_2+\cdots +a_k x_k=n]\Longleftrightarrow n_0 \mid n$$
$x_i=1, x_j=0 (j\neq i)$ のとき $a_1 x_1+a_2 x_2+\cdots +a_k x_k=a_i$ となるから、$n_0$$a_1, a_2, \ldots, a_k$ の公約数である。しかし先に示したことから
$n_0$$\gcd(a_1, a_2, \ldots, a_k)$ の倍数なので $n_0=\gcd(a_1, a_2, \ldots, a_k)$.

なお、Bezoutの補題から 倍数と約数:定理6 を示すこともできる。
実際 $d=\gcd(a, n)$ とおくと $sa+tn=d$ となる整数 $s, t$ がとれる。$n\mid ab$ のとき $ab=kn$ とおくと
より $k$$a/d=a/\gcd(a, n)$ の倍数であるから 倍数と約数:定理2 より $b=kn/a$$(na/d)/a=n/d$ の倍数である(逆に $b$$n/d$ の倍数ならば $ab=(a/d)n$$n$ の倍数である)。


Bezoutの補題 に関する議論は Trygve Nagell, Introduction to Number Theory, John Wiler & Sons, Inc. New York, 1951, Section 1.4, p.p.14--15 を参考とした。


G. H. Hardy and E. M. Wright, revised by D. R. Heath-Brown and J. H. Silverman, An Introduction to the Theory of Numbers, 6th Ed., Oxford University Press, 2008
G. H. Hardy and E. M. Wright, 訳: 示野 信一、矢神 毅, 数論入門I 原書6版, 数学クラシックス, 丸善出版, 2022
G. H. Hardy and E. M. Wright, 訳: 示野 信一、矢神 毅, 数論入門II 原書6版, 数学クラシックス, 丸善出版, 2022
D. P. Parent, Exercises in Number Theory, Springer-Verlag, 1984
Trygve Nagell, Introduction to Number Theory, Reprint Edition, American Mathematical Society (original: John Wiler & Sons, Inc.), 2001
Paulo Ribenboim, The New Book of Prime Number Records (3rd ed. pbk.), Springer, 2013
Edouard Lucas, Théorie des nombres, Gauthier-Villars, 1891
D. P. Parent, Exercices des théorie des nombres, BORDAS, 1978
H. C. Pocklington, The determination of the prime or composite nature of large numbers by Fermat's theorem, Proc. Cambridge Phil. Soc., 1914, 29
F. Proth, Théorèmes sur les nombres premiers, C. R. Acad. Sci., 87, 926
12 / 38