[解説] A = BQ + R ・・・・① これを移項すると
A – BQ = R ・・・・②
まず②を見ると、左辺のA、Bの公約数はすべて右辺Rの公約数であることが分かる。
次に①を見れば、右辺のB、Rの公約数はすべて左辺Aの公約数であると分かる。
これらのことから、A、Bの公約数とB、Rの公約数はすべて一致し、もちろん各々の最大公約数も一致する。
問題に対する解答は以上だが、ここから分かるのは「A、Bの最大公約数を知りたければ、B、Rの最大公約数を求めれば良い」という事実である。つまりこれを繰り返していけば数はどんどん小さくなっていく。これが前回23の互除方の原理である。