a÷b = q 余り r のとき、aとbの最大公約数はaとrの最大公約数と同じ。
またa÷b = q のときは、aとbの最大公約数はb。
これで終わる話だろ。

束好きだなあ笑