互除法（ユークリッドの互除法）の証明

教科書 p.149,177（教科書意味不明すぎて参考にならない）

最終的に証明したいのは、(a,b)の最大公約数と(b,r)の最大公約数が等しいことです。(rはaをbで割った余り)

そこで、(a,b)の最大公約数が(b,r)の最大公約数以下であり、かつ以上であることを証明します。

(a,b)の最大公約数をG₁、(b,r)の最大公約数をG₂とする。

aをbで割った商をp、余りをrとおくと、

a = bp+rと表せることより

(G₁はa,bの最大公約数、つまりa,bはG₁に何かの整数(= a',b')(互いに素)をかけたものであるから)

a = a'G₁,　b = b'G₁ (a',b'は互いに素)と表すことができ

(↑a'とb'共にG₁がかかっているからG₁はaとbの公約数、a',b'は互いに素であるからG₁はaとbの最大公約数)

a = bp+r を移項すると、

r = a − bp

a = a'G₁,　b = b'G₁を代入し、

r = a − bp = a'G₁ − b'G₁p = G₁(a' − b'p)より

G₁はbとrの公約数となる。

(↑b'とa' − b'p共にG₁がかかっているからG₁はbとrの公約数)

よって、aとbの最大公約数がbとrの公約数であることが言えるため、

(bとrの公約数G₂の中にaとbの最大公約数G₁が含まれる)

G₁≦G₂・・・(1)

また、b = b'G₂,　r = r'G₂と表すことができ

(b,rはG₂に何かの整数(= b',r')(互いに素)をかけたものであるからG₂はbとrの最大公約数)

a = bp+rより、

a = G₂(b'p + r')となる。

よって、G₂はaとbの公約数となる。

よって、bとrの最大公約数がaとbの公約数であることが言えるため、

(aとbの公約数G₁の中にbとrの最大公約数G₂が含まれる)

G₁≧G₂・・・(2)

(1),(2)より、G₁= G₂が成り立つ。

よって、(a,b)の最大公約数と(b,r)の最大公約数が等しい。

僕が書いといてあれなんですが、サイト見ながら分かりやすく書き加えていったんですが、勝手に　bとrの公約数がG₂((b,r)の最大公約数)、aとbの公約数がG₁((b,r)の最大公約数)になっているのが解せません。誰か教えてください。