Euclidean Algorithm(ユークリッドの互除法)
(a,b)はaとbの最大公約数を表します．例えば(4,10)=2, (5,10)=5などです． ユークリッドの互除法は a,b,q,rが自然数 a=bq+r が成り立つ時，(a,b)=(b,r) 」と表せます．例えば 「572=2*209+154なので (572,209)=(209,154)です．これは「縦209,横572の長方形を敷き詰めることのできる正方形は，横209,縦154の長方形を敷き詰めることができる．またその逆も成り立つ」ことから導けます．しかし残念ながら数研出版の教科書には，この図形的説明が載ってませんでした．この図を参考に図形的意味がわかって頂ければ幸いです．a,bは余り大きな数だとフリーズすることもあります．またa>b となる様にして下さい．(a<bでも動きますが，すこし見づらくなります)
ユークリッドの互除法と連分数には密接な関係があります．[Ford circle&Continued fraction（フォードの円と連分数)],[Continued Fraction&Rectangle（連分数と長方形)]を御覧ください．