aとbの最大公約数をkとする。 (1)aとbの最大公約数がbの時 a=a'bと書け、これを与式に代入すると、 a'b=bq+r r=b(q-a') rはbを約数に持ち、bにはbより大きい役数は存在しないため、 bはrとbの最大公約数である。 (2)aとbの最大公約数がbでないとき a=a'k b=b'k (a'とb'は互いに素、またはa'=1かつb'≠0,1,-1）とおける。 (a'=1かつb'≠0,1,-1は最大公約数がaの時のこと) これを与式に代入すると、 a'k=b'kq+r r=a'k-b'kq =k(a'-b'q) よってkはbとrの公約数である。 ここでb'とa'-b'qについて考える。 a'-b'qをb'で割ると、a'/b'-q ここでa'とb'は互いに素、またはa'=1かつb'≠0,1,-1であるため、 a'/b'は分数であり、qは整数であるため、a'/b'-qは分数である。 よってb'とa'-b'qは互いに素となる。 よってkはbとrの最大公約数である。 (1),(2)より、aとbの最大公約数は、bとrの最大公約数である