253と644の最大公約数を、ユークリッドの互除法を使って求めよう。

「AとB」の最大公約数は、「Bとr」の最大公約数と等しくなる のが互除法だよ。次々と割っていき、扱う2つの数を小さくしていこう。

644を253で割ると、
644 ＝ 253 ×2+ 138
644と253の最大公約数は、253と138の最大公約数と等しくなる よ。
さらに、
253 ＝ 138 ×1+ 115
138 ＝ 115 ×1+ 23
115 ＝ 23 ×5
より， 644と253の最大公約数は、115と23の最大公約数と等しく、23となる ね。