Add new comment

Arithmetic billiards

Mathematical billiards is an idealisation of what we experience on a regular pool table. In mathematical billiards the ball bounces around according to the same rules as in ordinary billiards, but it has no mass, which means there is no friction. There also aren't any pockets that can swallow the ball. This means that the ball will bounce infinitely many times on the sides of the billiard table and keep going forever.

One fascinating aspect of mathematical billiards is that it gives us a geometrical method to determine the least common multiple and the greatest common divisor of two natural numbers. Have a look at the Geogebra animation below (the play button is in the bottom left corner) and try to figure out how the construction works. If you would like to play the animation again, double click the refresh button in the top right corner. The two natural numbers are 40 and 15 in this case. The least common multiple of 40 and 15 equals 120, and the greatest common divisor is 5.

The basics

Here is the basic idea. Suppose we are given two positive whole numbers $a$ and $b$ , neither of which is a multiple of the other (the case where one is a multiple of the other is easy and is left to the reader). For the billiard table we take a rectangle whose sides have lengths $a$ and $b$ . We shoot a billiard ball from one corner (the bottom left in the figure above) making a 45 degree angle with the sides. The billiard ball bounces off the rectangle’s sides. It does not lose speed and, by the law of reflection, is reflected at a 45 degree angle each time it meets a side (thus the path only makes left or right 90 degree turns). The path of the billiard ball consists of line segments.

We claim that the ball eventually hits a corner and that the least common multiple of $a$ and $b$ is the length of the path the ball has traversed until it hit the corner, divided by $\sqrt{2}$ . If you decompose the billiard table into unit squares (squares of side length one), the least common multiple is equal to the number of unit squares which are crossed by the path.

We also claim that the path crosses itself. The first segment of the path contains the point of self-intersection which is closest to the starting point. The greatest common divisor of the two given numbers, we claim, is the distance from the starting point to the closest point of self-intersection, divided by $\sqrt{2}$ . It is also equal to the number of unit squares crossed by the piece of the path from the starting point to the first point of self-intersection.

Mirror billiards

While looking at an object in a mirror, you have the impression that the object is behind the mirror. Notice that three points are aligned: the point marking your position, the point on the mirror where you see the reflection of the object and the (imaginary) point behind the mirror where you believe the object to be. To prove our claims above, we are going to exploit this simple idea, the mirror being one side of the billiard table.

The least common multiple of $a$ and $b$ , written as $lcm(a,b)$ , is the smallest natural number that is a multiple of both $a$ and $b$ . We can write it as $ma=nb$ for some positive whole numbers $m$ and $n$ . For example, if $a=4$ and $b=6$ , then $lcm(a,b)=12$ and can be written as

$12 = 3\times 4 = 2 \times 6.$

In this case $m=3$ and $n=2$ .

Given our two numbers $a$ and $b$ , none of which is a multiple of the other, start by forming a square with sides of length $lcm(a,b)$ . Notice that this can be decomposed into $m\times n$ rectangles with sides of length $a$ and $b$ . That’s because $a$ fits into $lcm(a,b)$ a total of $m$ times and $b$ fits into $lcm(a,b)$ a total of $n$ times. Because $ma=nb$ is the least common multiple of $a$ and $b$ our square is the smallest square that can be tiled by rectangles with sides of lengths $a$ and $b$ in this way. We’ll call the bottom left of these rectangles $R$ and the top right $S$ .

In this example a=4 and b=6. Their least common multiple is 3x4=2x6=12, so the square has sides of lengths 12. It contains 3x2=6 rectangles.

Now draw the diagonal $d$ of the square which starts at the bottom left corner and ends in the top right corner.

From $d$ we’ll now create a zig-zag path $t$ , which lies entirely within the bottom left rectangle $R$ , using repeated reflection. This path $t$ will turn out to be the path of an arithmetic billiard ball moving within the rectangle $R$ .

We start with the top right square $S$ and reflect it in the side that is crossed by the diagonal $d$ , which it shares with a neighbouring rectangle (the rectangle below $S$ in our example). Let’s write $S^{\prime }$ for this rectangle.

Reflecting the square S in its bottom side reflects part of the diagonal into the rectangle below S.

Now reflect $S^{\prime }$ in the other side that is crossed by $d$ (its left side in our example), not the one that would get us back to $S$ .

Reflecting S' in its left side.

Keep going like this, reflecting rectangles across sides crossed by $d$ , until you reach the bottom left rectangle $R$ . The repeated reflections transform the diagonal $d$ into the zig-zag path $t$ .

The last reflection results in the path t entirely contained in the rectangle R.

The path $t$ is exactly the path of a ball shot from the bottom left corner of $R$ at 45 degree angles to the sides of $R$ . You can verify this using the animation below.

To prove that this is really the case, recall that the ball will make 90 degree turns whenever it hits a side of $R$ . It’s quite easy to see that the path $t$ does the same. This is best explained using a picture:

The path t makes 90 degree turns when it meets a side of R.

Our path $t$ ends at the point that comes from repeatedly reflecting the top right corner of $S$ in sides of rectangles, so the end point of $t$ is a corner of $R$ .

Now the length of $t$ is equal to the length of the diagonal $d$ . The length of the diagonal of any square is $\sqrt{2}$ times its side length (this comes from Pythagoras’ theorem). Therefore

$|t| = \sqrt{2} lcm(a,b),$

where $|t|$ stands for the length of $t$ . Rearranging, we have that

$lcm(a,b) = \frac{|t|}{\sqrt{2}},$

which is exactly what we were trying to prove.

Our method worked perfectly for our example, but can we be sure it works for general values of $a$ and $b$ (that aren’t multiples of each other)? The only thing that could go wrong is that the diagonal $d$ of the square meets the corner of a rectangle which lies in the interior of the square. If that were the case, we wouldn’t know which of the two sides that meet at the corner to reflect in.

We’ll show that this can’t happen. It’s quite easy to convince yourself that any point $p$ on the diagonal determines a square: simply drop a line down vertically until you hit the bottom edge of the original square, and draw a horizontal line over to the left until you hit the left edge of the original square.

Any point on the diagonal of a square determines a smaller square.

If such a point were also the corner of one of the rectangles, then our small square would be tiled by rectangles with sides of lengths $a$ and $b$ . But this is impossible: as we noted above, the square with side length $ma=nb$ is the smallest square that can be tiled in this way.

We’ve shown that $lcm(a,b)$ is equal to the length of the path $t$ divided by $\sqrt{2}$ . Let’s move on to the unit squares.

The unit squares crossed by the path

To count the number of unit squares (squares with sides of length $1$ ) the path $t$ crosses, we equip our rectangle $R$ with a coordinate system. The vertical axis runs along the left vertical side of $R$ and the horizontal axis runs along the bottom side of $R$ . The coordinates of the corners of the unit squares are whole numbers.

The rectangle R with its coordinate systems. Coordinates of the corners of unit squares that lie on t are shown in red.

It’s clear that if $t$ crosses a unit square, it does so along a diagonal. You can also convince yourself that if the corner of any unit square lies on $t$ , then its coordinates must add up to an even number. Any unit square only has two corners whose coordinates add up to an even number and these are diagonally opposite each other. Therefore $t$ can only pass along one of the two diagonals of a unit square.

We leave it up to you to show that $t$ never passes along the diagonal of a unit square twice, neither in the same direction, nor in the opposite direction. You will need to show that the end point of $t$ is different from its starting point. To do this, note that at least one of $m$ or $n$ must be odd, and that the end point of $t$ comes from repeatedly reflecting the top right corner of the rectangle $S$ .

We now know that $t$ never crosses a unit square more than once and always does so along the diagonal. Since the diagonal of a unit square has length $\sqrt{2}$ , the number of squares crossed by $t$ is

$\frac{|t|}{\sqrt{2}} = \frac{\sqrt{2} lcm(a,b)}{\sqrt{2}} = lcm(a,b),$

just as we claimed above.

The greatest common divisor

We claimed that the greatest common divisor of $a$ and $b$ $gcd(a,b)$ is the distance from the starting point of $t$ to the closest point of self-intersection, divided by $\sqrt{2}$ . It is also equal to the number of unit squares crossed by the piece of the path from the starting point to the first point of self-intersection.

Let’s first assume that $gcd(a,b)=1$ . In this case, the least common multiple of $a$ and $b$ is the product $ab$ (see if you can prove this for yourself). By our previous result, the number of unit squares crossed by our path is also $ab$ . Since the sides of the rectangle $R$ have lengths $a$ and $b$ , there are $ab$ unit squares in total. And since the path crosses no unit square more than once, it must cross all $ab$ unit squares in this case.

In this example a=3 and b=8. The greatest common divisor is 1 and the least common multiple is 24.

We already know that the corners of unit squares that lie on $t$ all have coordinates that add to an even number. Conversely, the fact that every unit square is crossed by $t$ means that every point with coordinates that add to an even number lies on $t$ .

This means that the points with coordinates $(0,0)$ , $(2,0)$ and $(0,2)$ and $(2,2)$ all lie on $t$ . This can only happen if $(1,1)$ is a self-intersection point of $t$ .

The point $(1,1)$ is therefore a point at which $t$ intersects itself, and it’s the point closest to $(0,0)$ along $t$ . The distance from $(0,0)$ to $(1,1)$ along $t$ is $\sqrt{2}$ . Divide this by $\sqrt{2}$ and you get $1$ , the greatest common divisor of $a$ and $b$ (by our assumption above). The number of unit squares crossed on the way from $(0,0)$ to $(1,1)$ along $t$ is also equal to $1$ . This proves our original claim for $gcd(a,b)$ for the case in which $gcd(a,b) =1$ .

If $gcd(a,b)\neq 1$ , then we can rescale the whole figure by a factor $gcd(a, b)$ : dividing $a$ and $b$ by their greatest common divisor, we obtain two positive integers whose greatest common divisor is $1$ . We can repeat the construction from above for these two integers, and then scale the picture up by multiplying each axis in our coordinate system by $gcd(a,b)$ . Unit squares then become squares of side length $gcd(a,b)$ . All geometric properties not related to the length (the shape of the path, in which corner the billiard ball lands, etc...) are unaffected by the rescaling.

In this example a=9 and b=24. The greatest common divisor is 3. Dividing through by 3, we get 3 and 8, the numbers used in the example above. Scaling up the picture from the previous example by a factor of 3 then gives us this picture. The unit squares from the previous picture turn into larger squares of side length 3, made up of 3x3=9 unit squares each.

It then follows that the self-intersection point closest to the starting point lies on the first segment of the path at distance $\sqrt{2}gcd(a, b)$ from the starting corner and that $gcd(a, b)$ is the number of unit squares crossed by the first segment of the path from the starting point to the closest point of self-intersection.

Questions for the reader

If you enjoyed this article, then here are some questions you might want to explore yourself:

If one of the two given numbers is a multiple of the other, what is the shape of the arithmetic billiard path?
For which numbers does the arithmetic billiard path end in the corner opposite to the starting point?
What are the symmetries of the arithmetic billiard path (as a geometrical figure)?

About the author

Antonella Perucca is Professor for Mathematics and its Didactics at the University of Luxembourg. She is a researcher in number theory and invents mathematical exhibits (for example the "Chinese Remainder Clock"). To find out more, explore her webpage. She would like to thank Andrew Bruce for help with the article.

Plus.Maths.org