09/02/05 00:37:05
>>953
A > Bとする
縦の長さがA、横の長さがBの長方形を一辺の長さがdの正方形でタイル張り可能か考える
きれいにタイル張り可能ならdはAとBの公約数、出来なければdは公約数でない
AをBで割って商がq、余りがrとする
元の長方形を、q枚の正方形（一辺B）と1枚の小長方形（縦r、横B）が縦に並んだものと考える
元の長方形がタイル張り出来たなら、小長方形もタイル張り出来ている
つまり、dがAとBの公約数なら、dはBとrの公約数でもある
逆に、小長方形がタイル張り出来たとする
一辺Bの正方形もタイル張り出来るから、元の長方形全体全体がタイル張り出来る
つまり、dがBとrの公約数なら、dはAとBの公約数でもある