最後の余りが最大公約数になる理由
この理由は次のように説明できます。
385と105の最大公約数をnとしましょう。
385=n×a 105=n×b とすると
1. 式より、n×a=n×b×3+70 ⇔ n× (a−3b) =70
このことより、nは70の約数にもなります。
2. 式より、n×b=n×(a−3b)×1+35 ⇔ n (4b−a)= 35
このことより、nは35の約数にもなります。1.と2.の式より、nは70と35の公約数になります。
3. 式より、70は35で割り切れてしまいますので、70と35の最大公約数は35ですので、n=35となります。
こうして、求める最大公約数はn=35というわけです。
以上で行ったプロセスをユークリッド互除法と呼んでいます。これは、分数を生みだす原理でもありました。
ユークリッド互除法は、分数を生みだす原理でもある photo by gettyimages分数では、基準1と与えられた数との共通尺度を求める方法でしたが、ここでは与えられた二つの数（自然数）の共通因数を求める方法にもなるわけです。つまり、2数の最大公約数を求める方法の一つでもあるのです。
