gcd(a,b)=gcd(|a|,b)=gcd(a,|b|)=gcd(|a|,|b|)を証明してみたい

前置き

ある日、プログラムの勉強でインターネットを調べていた時、以下のような問題を見つけた。

さっそく解いてみようとして、手が止まった。なぜなら今までgcdを求めるときの入力はもっぱら自然数であり、入力が整数のときにgcdを求めた経験は無かったからだ。

この問題を解くために色々と調べたところ、 proofwiki に整数a,bに対して以下の式が成り立つというページがあった。

※これを利用すれば、負の値を考えずに済む。

この定理を使用することで前述の問題を解くことが出来たのだが、
これが本当に成り立つ定理なのか疑問に思った。(書かれていた証明は難しく、あまり理解できなかった。)
その後、1週間くらいかけて数式を弄り回してみたところ、自分でも納得できる証明を作ることが出来たため、以下にそれを記す。

証明

まず、以下の補題2を証明する。

補題2の証明

まず、$a$の約数に$k$があるということは、
除法の原理 より$a = ck$ となるような整数$c$がただ一つ存在する。
(ここで、$a$は割られる数、$k$は割る数、$c$は商である)
ここで、両辺を-1倍する。 等号の性質 から、等しさは変わらない。
すると、
$-a = -ck$
右辺を整理して、
$-a = (-c)k$
この式と除法の原理の式を比較すると、
$-a$の約数は$k$であるということを表している。
よって、$a$にある約数$k$が存在するとき、その$k$は$-a$の約数でもある。...(1)

そして、(1)は$a$の約数すべてにおいて言える。...(2)

(1)と(2)より、$a$の約数の集合$K$から任意の約数$k$を取り出したとき、
それは$-a$の約数の集合$K'$にも必ず存在する。
よって$K = K'$である。(証明終)

この補題2を用いて、定理1を証明しよう。

定理1の証明

まず、$gcd(a,b)$において、
$a$の約数の集合を$A$、
$b$の約数の集合を$B$とする。
すると、 公約数 と 最大公約数 の定義から
$gcd(a,b)=max(A \cap B)$である。...(3)

ここで、
$-a$の約数の集合を$A'$、
$-b$の約数の集合を$B'$とする。
補題2を用いて(3)を変形すると、
$max(A \cap B)=max(A' \cap B)=max(A \cap B')=max(A' \cap B')$ ...(4)
となる。

さらに(3)を逆に用いて(4)を変形すると、

$gcd(a,b)=gcd(-a,b)=gcd(a,-b)=gcd(-a,-b)$が成り立つ...(5)

あとは、
(5)を用いて、全ての場合において定理1を証明すればよい。

に気を付けて、場合分けを行う。

$a\geqq0,b\geqq0$のとき、
$gcd(a,b),gcd(|a|,b),gcd(a,|b|),gcd(|a|,|b|)$
を変形すると、
すべて$gcd(a,b)$となる。
$gcd(a,b)=gcd(a,b)$より、
定理1は真。

$a\geqq0,b<0$のとき、
$gcd(a,b),gcd(|a|,b),gcd(a,|b|),gcd(|a|,|b|)$
を変形すると、
$gcd(a,b),gcd(a,b),gcd(a,-b),gcd(a,-b)$となる。
(5)より、$gcd(a,b)=gcd(a,-b)$
となり、定理1は真。

$a<0,b\geqq0$のとき、
$gcd(a,b),gcd(|a|,b),gcd(a,|b|),gcd(|a|,|b|)$
を変形すると、
$gcd(a,b),gcd(-a,b),gcd(a,b),gcd(-a,b)$となる。
(5)より、$gcd(a,b)=gcd(-a,b)$
となり、定理1は真。

$a<0,b<0$のとき、
$gcd(a,b),gcd(|a|,b),gcd(a,|b|),gcd(|a|,|b|)$
を変形すると、
$gcd(a,b),gcd(-a,b),gcd(a,-b),gcd(-a,-b)$となる。
(5)より、$gcd(a,b)=gcd(-a,b)=gcd(a,-b)=gcd(-a,-b)$
となり、定理1は真。

以上より、全ての$a,b$の場合で定理1は真となったため
$gcd(a,b)=gcd(|a|,b)=gcd(a,|b|)=gcd(|a|,|b|)$
は成り立つ。(証明終)