Reflection and greatest common divisors

[Ben]

I read an article in a Martin Gardner book once about how you can calculate the gcd of two numbers, a and b, by setting up a rectangle of dimensions axb and letting a line “reflect” around inside the rectangle until it hit the gcd. In fact, someone actually build a device which calculates gcd’s by reflecting light off of mirrors.

Could someone explain to me how this works? I can’t find the book at the local libraries, nor do they have back issues of SciAm.

Also, I seem to remember Gardner applying the technique to a hexagonal grid as well, to find the gcd of three numbers. How does that work?

-Ben

[jcgmoi]

Ben: I too vaguely remember this. I think it was in a discussion of analog computing devices but I’m afraid the details are gone.

Maybe this rough index of Gardner’s books will help you find the original article.

[rowrrbazzle]

The mirror device is described in the article “The Lattice of Integers”, reprinted in “Sixth Book of Mathematical Diversions from Scientific American” by MG. It was originally published in 1963. My copy is apparently a 1983 reprint of the book by the U. of Chicago Press. According to Amazon, the book is now out of print.

The device was patented by Andres Zavrotsky of the U. of the Andes in Venezuela. U.S. patent number 2978816 on April 11, 1961.

From the article:

Four mirrors with integral scales on their edges can be adjusted to form a rectangle with sides equal to the pair of numbers under investigation. A pencil of light is introduced through a crack at one corner, as shown. It rebounds at an angle of 45 degrees from the corner - the zero point on the two scales meeting at that corner - and continues its path from mirror to mirror until it terminates at one of the other three corners. The illuminated mark closest to the corner of origin of what Zavrotsky calls the “optical billiard” on the rectangle’s long side is twice the gcd.

This article doesn’t say anything about other polygons, so it may not be the same one you saw.

[Cabbage]

I think what you’re looking for is in Sixth Book of Mathematical Games from Scientific American.

There’s an article in there about using these graphs to solve “vessel problems”, you know, the kind of problems like: You have a 7 quart vessel and a 5 quart vessel. How do you measure 3 quarts?

This type of problem is closely tied to greatest common divisors; given two vessels, one holding a units, the other holding b units, the greatest common divisor of a and b is the smallest amount that can be measured. For example, if you have a vessel holding 12 oz., a vessel holding 30 oz., then 6 oz. is the smallest amount you can use those to measure.

Anyway, what’s described in the article is a method of solving these types of problems using a parallelogram and having a ball, beam of light, whatever, bounce around.

It’s really hard to describe without pictures, but I’ll try. Picture a parallelogram–top and bottom sides horizontal, each 7 units long; left and right sides 5 units long each, and making an angle of 60[sup]o[/sup] to the horizontal. Mark off unit intervals on the sides, like you would in a standard xy-plane (except the y axis is tilted).

Now we put a ball inside the parallelogram. At any moment, the position of the ball tells how many quarts are in either vessel (just like in standard coordinate axes).

Start the ball in the bottom left corner ((0,0)–corresponding to the state of nothing being in either vessel). Roll the ball to the right along the bottom side (filling up the 7 quart vessel). The ball hits the corner ((7,0)–vessel full), then bounces off and hits the top side at the point (2,5)–the 7 quart vessel has been used to fill the 5 quart vessel. And so on.

The smallest point the ball hits on the x or y-axis corresponds to the greatest common divisor of the two numbers–in this example, eventually the ball will hit both (1,0) and (0,1), since 1 is the gcd of 7 and 5.