2辺の長さが a, b である長方形から，
無駄なく，同じ大きさの正方形を切り取りたい。
最も大きな正方形の一辺の長さはいくらか。

求める長さを g とすると，
無駄なく ということから，g は a の約数である。
同じことが b についてもいえるから，
g は a と b の公約数である。
最も大きな ということから，g は a と b の最大公約数である。

いま，a > b とする。
一辺の長さが b である正方形をこの長方形からできるだけ切り取る。
q 個切り取ったとする。
r = a - bq として， r = 0 ならば， b = g である。
0 < r < b のとき， 2辺の長さが，b, r である長方形が残る。
問題は，この長方形で同じことを考えることに帰着できる。

72 と 35 の最大公約数を求める

a	b	q	r
72	37	1	35
37	35	1	2
35	2	17	1
2	1	2	0

よって，最大公約数は 1