Posted by: danb | November 13, 2008

Spirographs: An Application of Modular Arithmetic

I was trying to find some applications of what we have been covering in class, and I came across this problem, which deals with spirographs.  (If you want to see some pictures of spirographs, search it on Google images.)  This problem can be solved using modular arithmetic.  It’s not exactly the practical example I was looking for, but it is still a pretty cool use of modular arithmetic.

In a spirograph toy you first select two circular gears. Keeping one gear stationary, you let the second gear travel around the first one until it arrives back at its initial position and orientation. By tracing the path with a pen through a hole in the second gear you can make designs like the one above. Assuming the notches in the gears are equally spaced apart, and that there are x notches in the stationary gear, and y (y<x) notches in the moving gear, how many trips around the first gear will the second gear need to make before it arrives back at its initial position and orientation?

At first I was confused by the problem, but then after thinking in terms of modular arithmetic it became pretty simple.  My first step was to think of an example.  I let x=5 and y=4.  I numbered each groove on x (there are 5 grooves if there are 5 notches), and each notch on y.  Assuming notch 1 starts in groove 1, then after one rotation around the stationary gear, notch 2 will be in groove 1.  After a second rotation, notch 3 will be in groove 1.  After a third, notch 4 will be in groove 1.  After a fourth, notch 5 will be there.  And finally, after a fifth, notch 1 will be back in groove 1.  I was writing this out and noticed that it is the order of 4 under addition in Z_5.  In other words, under addition, 4^5=1 in Z_5.  But, this is how many rotations the moving gear makes, not how many trips around the stationary gear it makes.  But,  if it rotates 5 times, that means there were a total of 5×4=20 notches touched.  And since the stationary gear has 5 notches, 20/5=4.  So it makes 4 trips around.

The general form is to find the order of y in Z_x.  Then, multiply that by y and divide by x.  For example, if there are 6 grooves in the stationary gear and 3 in the moving gear, the order of 3 in Z_6 is 2.  Then, 2×3/6=1.  This makes sense because if you look at what groove is going to what notch, it only takes one cycle around the 6-notch gear to get back to the identity:

1-1

2-2

3-3

1-4

2-5

3-6

——

1-1

etc.

So the final answer is, in Z_x, ord(y)(y/x).

There you have it.  An application of modular arithmetic.