ユーグリッド互除法について

競技プログラミングでよく最大公約数がらみの問題が出てそのたび解けずにおります。なので、ここらでいっちょ自分で簡単にまとめていこうかなと。
ではいきます。
＊どんどん追記していく自分用メモになります。

~~ユーグリッド互除法の簡単な証明と忘れがちな定理

まず、簡単な説明・証明から

自然数a,bについて。aをbで割った商をq,余りをrとおくと、aとbの最大公約数とbとrの最大公約数は等しい

（念のため式）

a = b * q + r

・証明（チョー丁寧）

a,bの最大公約数をG、q,rの最大公約数をgとおく。
a = b * q + r 
であるので、右辺はgで割り切れる（[右辺]＝g (b*q' + r')）-  ①
なので左辺、つまりaも割り切れるということなので、Gはgの約数となる。
①の式よりG,gの大小関係は
　　　　G >= g - ②
となる。

次に、与式を次のように変形する。
a - b * q = r
上記と同様に考える。
右辺はGで割り切れるので、gもGで割り切れ、(a' - b' * q)G = gより
　　　　g  >= G - ③
である。
②、③より
G = g であることが証明されました。
〼

一応コードも書いておきます。

long long GCD(long long x, long long y) {
    if(x<y) swap(x,y);
    if(y==0)return x;
    return GCD(y,x%y);
}

以降、上記のアルゴリズムをGCDと表記していきます。

ここから詰まったものを書き留めていきます。

最小公倍数

求め方自体は以前から知っていたのですが、少しためになるものも見つけたのでメモ。
まず、A,Bの最大公約数をG,最小公倍数をＬとすると、

G * L = A *B 

が成り立つというもの。これは以前から知っていたので最小公倍数を求めるときは

A * B / G

と反射で計算。しかし、ここでA * Bがオーバーフローする可能性は十分ありますね。そんな時は。。。

A / G * B

とするとその可能性をつぶせます。このテクは押さえておかないといつか痛い目を見るなと思ったのでメモ。

~A≡B(mod X ) の時　GCD(A,X) = GCD(B,X)となる。

さてもう一度

A≡B(mod X ) の時　GCD(A,X) = GCD(B,X)となる。

何回見ても？？？となってしまいます。
でも、文にするとわかるんですよね。

AをXで割った余り　＝　BをXで割った余り
とは、つまり
A = X * S + T 
B = X * S' + T

とすると、まんま冒頭で示したユーグリッド互除法なので「当たり前じゃん」となります。

そう思いまよね？ではもう一度。。。

A≡B(mod X ) の時　GCD(A,X) = GCD(B,X)となる。

。。。は？

まあ、これができると何がいいかというと

GCD(A,X) = GCD(A-X,X)

となるので、差をとる問題では「最大公約数使えねえかな？」なんてアンテナを張れるのです。（この式がうまく引き出せるようになっていればよさげ）