The geometric Euclidean algorithm: repeatedly subtract the smaller side from the larger, tiling the rectangle. The GCD is the side of the final square.