ユークリッドの互除法、公約数の性質

約数(divisor)

#

約数とは整数\(a \in \mathbb{Z}\)に関して\(a=dk\)となるような数\(d\)のことをいう。

このとき、 $$ d \space | \space a, \space d \space / \space a $$ などと表す。

\(|\)の左側の数を何倍かすれば\(|\)の右側の数になるという意味だ。

言い換えると\(d \space | \space a\)は\(d\)が\(a\)を割り切ることを記述している。

公約数(common divisor)

#

\(a,\space b, \space d \in \mathbb{Z}\)に関して $$ d \space | \space a \land d \space | \space b $$ のとき、つまり、\(d\)が\(a\)と\(b\)の両方を割り切るとき、\(d\)を\(a,\space b\)の公約数であるという。

common factorと呼ばれる場合もある。

最大公約数(greatest common divisor, gcd)

#

約数の中で最も大きいものを最大公約数という。

\(a, \space b\)の最大公約数は\(gcd(a,\space b)\)のように記述されることが多い。

\(\gcd(x, \space 0)=x\)である。
なぜなら\(x\)の最大の約数は\(x\)であり、\(x \space | \space 0 \)だからである。

公約数の性質1

#

$$ \{z_1, \space z_2, \space \dots, \space z_n\}, \space z_i \in \mathbb{Z} \space (1 \leqq i \leqq n) $$ に関して各\(z_i\)が\(d \space | \space z_i\)を満たすとき、 $$ d \space | \space (a_1 z_1 + \dots + a_n z_n) \quad a_i \in \mathbb{Z} \space(1 \leqq i \leqq n) $$ がなりたつ。

具体例

#

よくよく考えると当たり前(馴染んだ)話である。

例えば \(9, \space 18, \space 33\)を考えると、 $$ 3 \space | \space 9 \enspace \land \enspace 3 \space | \space 18 \enspace \land \enspace 3 \space | \space 33 $$ であり、 $$ 3 \space | \space (a_1 9 + a_2 18 + a_3 33) $$ である。

なぜなら、\(9, \space 18, \space 33\)はすべて\(3\)の倍数であり、 $$ a_i \cdot 3の倍数 $$ も\(3\)の倍数になるので、その和も\(3\)の倍数であるからだ。

その一般的な場合をまとめて表したのが上述の記述だ。

証明

#

\(\forall a_i \in \mathbb{Z} \space (1 \leqq i \leqq n)\)に関して \((a_1 z_1 + \dots + a_n z_n)\)を考える。

各\(z_i\)に関して、仮定より\(d \space | \space z_i \)なので\(z_i = d b_i\)を満たす\(b_i \in \mathbb{Z}\)が存在する。

よって、 $$ (a_1 z_1 + \dots + a_n z_n) = (a_1 d b_1 + \dots + a_n d b_n) \\ = (a_1 b_1 + \dots + a_n b_n)d \\ $$ と変形することができ、\( (a_1 b_1 + \dots + a_n b_n) \in \mathbb{Z}\)なので $$ d \space | \space (a_1 z_1 + \dots + a_n z_n) $$ が示される。

公約数の性質2

#

\(a,\space b \in \mathbb{Z}\)に関して、 $$ a = bq + r $$ を満たすような\(q, \space r \in \mathbb{Z}\)が存在するとき、\(\gcd(a,\space b)=\gcd(b, \space r)\)である。

関連: \(a=bq+r\)の存在 🔗division algorithm

証明

#

最大公約数の定義より $$ \gcd(a ,\space b) \space | \space a \enspace \land \enspace \gcd(a ,\space b) \space | \space b $$ である。

ここで、上述の定理を適用すると、 $$ \gcd(a,\space b) \space | \space (1 \cdot a - bq) $$ を得る。

\(a = bq + r \)より\(a-bq = r\)なので $$ \gcd(a,\space b) \space | \space r $$ である。

整理すると、いま、\(\gcd(a,\space b)\)は\(a, \space b, \space r\)の公約数である。

よって、\(\gcd(a, \space b) \leqq \gcd(b, \space r)\)である。

なぜなら\(\gcd(b,\space r)\)は\(b,\space r\)の公約数の中で最大のものであり、いま、\(\gcd(a,\space b)\)は\(b,\space r\)の公約数なのだから、\(\gcd(b, \space r)\)はそれ以上(\(\leqq\))である。

\(b, \space r\)に関して同様の議論¹をすると\(\gcd(b, \space r) \leqq \gcd(a, \space b)\)を得るので $$ \gcd(b, \space r) = \gcd(a, \space b) $$ を得る。

ユークリッドの互除法(Euclidean algorithm)

#

ユークリッドの互除法とは最大公約数を機械的に定められた手順で求めることのできるアルゴリズムである。

\(a,\space b \in \mathbb{Z}\)に関して\(\gcd(a,\space b)\)を求める。

\(a \geqq b\)とする。(\(a < b\)の場合は入れ替えて議論すれば良い)

まず、🔗division algorithmで $$ a= bq+r \enspace (0 \leqq r < b) $$ を満たす\(q, \space r\)を得る。

ここで、🔗上述の公約数の性質より、\(\gcd(a, \space b) = \gcd(b, \space r)\)である。

よって、\(\gcd(a,\space b)\)を求めるためには\(\gcd(b, \space r)\)を求めればよい。

\(\gcd(b, \space r)\)に関して同様の操作を行い、その結果に関して更に同様の操作を行うことを続ければ良い。

つまり、 $$ a = bq_1 + r_1 \implies \gcd(a, \space b) = \gcd(b, \space r_1) \\ \Downarrow \\ b = r_1 q_2 + r_2 \implies \gcd(b, \space r_1)=\gcd(r_1, \space r_2) \\ \Downarrow \\ r_1 = r_2 q_3 + r_3 \implies \gcd(r_1, \space r_2) = \gcd(r_2, \space r_3) \\ \Downarrow \\ \vdots $$ のような操作を続けるということなのだが、🔗division algorithmの\((0 \leqq r < b) \)に着目すると $$ b > r_1 > r_2 > r_3 > \dots > r_k = 0 $$ となるので有限回数の操作で\(r_k=0\)になることがわかる。

\(\gcd(r_{k-1}, \space r_k) = \gcd(r_{k-1}, \space 0)=r_{k-1}\)なので\(\gcd(a, \space b)= r_{k-1}\)である。

prolog

#

練習のためにprologで書いた。

シンプルに実装できる。

% 再帰の終了条件
my_gcd(X, 0, X).

% アルゴリズム本体
my_gcd(X, Y, G) :-
	Y \= 0,
	Z is X mod Y,
       	my_gcd(Y, Z, G).

が、実際のコンピューターでは速くなってきてるとはいえ除算(mod)は遅いのでシフト演算やビット演算を駆使して書くほうが高速である。

C++コンパイラの実装(clang, std::gcd)などではそういった実装がされている。

感想

#

中学生だか高校生の頃に本でユークリッドの互除法についての記述を目にしたが、分けのわからないものにしか見えず、まともに読むことすらしなかった(できなかった)のを思い出した。