ユークリッド互除法

整数a,bの最大公約数を考えます。

gcd(a,b)=d(最大公約数)
aをbで割った商がq,余りがrとすると
a=bq+r(除法定義)
r=a-bq(加法逆元)…①

最大公約数の定義よりbを共有するgcd(a,b)とgcd(b,r)は約数を共有…②

a=a’･gcd(a,b)(最大公約数)…③
b=b’･gcd(a,b)(最大公約数)…④
①の式に③④を代入
r=a-bq(①)
r=a’･gcd(a,b)-b’･gcd(a,b)(③④代入)
r=gcd(a,b)(a’-b’)(分配法則)…⑤

⑤はgcd(a,b)がrの約数であることを示しています。

また、gcd(a,b)の性質上、それは同時にbの約数でもあります。

gcd(a,b)はbとrの公約数なので、a,bの最大公約数との間には
gcd(a,b)≤gcd(r,b)…※1
が成り立ちます。

同様に
r=r’gcd(r,b)
b=b’gcd(r,b)

①へ代入。
a=q･b’･gcd(r,b)+r’･gcd(r,b)(代入)
a=gcd(r,b)(q･b’+r’)(分配法則)

gcd(r,b)はaの約数なので、
gcd(r,b)≤gcd(a,b)(最大公約数)…※2
が成り立つ。

※1※2より
gcd(r,b)=gcd(a,b)(反対称関係)

最大公約数

勝手に使った概念のお勉強。

最大公約数は一言で言えば二つの整数の「約数の内で最大のもの」。

約数

整数 a ≠ 0 が N の約数であるとは、「ある整数 b をとると N = ab が成立することである」であるが、条件「a ≠ 0」を外すこともある。このときは、N = 0 のときに限り 0 も約数になる。約数が無数にある整数は 0 だけである。

ウィキペディア

最大公約数

最大公約数（さいだいこうやくすう、英: greatest common divisor[注釈 1]）とは、すべての公約数を約数にもつ公約数である。

素朴な定義
以下では、自然数は

$\displaystyle 0$ を含むとし、$\displaystyle a$ が $\displaystyle b$ を割り切ること（つまり $\displaystyle b=ca$ となる自然数 $\displaystyle c$ が存在すること）を$\displaystyle a\mid b$ と表す。

写像 $\displaystyle \gcd \colon \mathbb {N} ^{n}\to \mathbb {N} ;(a_{1},\dots ,a_{n})\mapsto d$ を

すべての $\displaystyle 1\leqq i\leqq n$ に対して $\displaystyle d\mid a_{i}$ であり、

すべての自然数 $\displaystyle b$ に対し、すべての$\displaystyle 1\leqq i\leqq n$ に対して $\displaystyle b\mid a_{i}$ ならば $\displaystyle b\mid d$ となるように定める。

$\displaystyle d$ を$\displaystyle a_{1},\dots ,a_{n}$ の最大公約数といい、$\displaystyle d$を$\displaystyle a_{1},\dots ,a_{n}$ の最大公約数といい、$\displaystyle \gcd(a_{1},\dots ,a_{n})$ や $\displaystyle (a_{1},\dots ,a_{n})$ と表す。

ウィキペディア