Search:

Billiard Loops and the GCD:

Let {$m,n\in\mathbb N$} be the dimensions of a rectangle. Then the number of loops on the rectangle is equal to {$(m,n)-1$}, one less than the greatest common divisor of {$m$} and {$n$}.

Proof: Let {$d=(m,n)$} and {$m=jd$}, {$n=kd$}, with {$j$} and {$k$} relatively prime. Then any loop on the rectangle

can be traced out on the reflections as we traced the path (as in the proof of Billiards and the LCM),

except that in covering a length of {$jkd$} (the side of the square), the loop ran one of the dimensions, possibly both, an odd number of times, ending up on a different side of the rectangle. This is because the loop ran the length {$k$} times and the width {$j$} times and {$j$} and {$k$} can't both be even since {$(j,k)=1$}.

To return to its starting spot,

it must travel {$jkd$} further.

The paths and loops together cover the area of the rectangle twice (each unit square is traversed once in each diagonal direction), so the sum of the lengths must be {$2jkd^2$}. The two paths from the corners each cover {$jkd$}. That leaves {$$2jkd^2-2jkd$$} for the loops. Each loop is {$2jkd$} long, so the number of loops is {$$\frac{2jkd^2-2jkd}{2jkd}=d-1,$$} which is what we wished to prove.

Print - Search
Page last modified on January 01, 2014, at 01:53 AM