# All Geared Up

## Joseph DeVincentis

It should be apparent upon analyzing the picture that there are two groups of gears here. The six small gears in a straight line at the top have mixed letters of the alphabet on them, while the 10 larger gears crammed into the rest of the image have all the letters in alphabetical order, without skipping any on most gears, and only skipping some of the more difficult letters on the smaller ones of these gears.

Consider the small gears first. Most of the letters are difficult ones and there are few vowels available, and as a result there is only one word that can be spelled across them: ANSWER. You can confirm this with word lists or get it from the flavor text, which specifically tells you to find the first answer, that is, the first time the gears spell ANSWER when turning in the direction indicated by an arrow next to one gear.

How far do you have to turn the gears to make them spell out ANSWER? Turning the first gear in the direction of the arrow, you need to turn it 4 notches to bring the A up to the mark. But the rest of the word won't be spelled out, so you will need 4 plus some multiple of 13 to get A on top another time. The second gear will turn in the opposite direction, so you need to rotate it 1 notch plus a multiple of 11. And so you need to solve for X such that:

- X = 4 mod 13
- X = 1 mod 11
- X = 2 mod 9
- X = 7 mod 8
- X = 3 mod 7
- X = 2 mod 5

The Chinese Remainder Theorem solves problems of exactly this type. Writing the set of equations as *X = a _{i}* mod

*n*, and letting

_{i}*N*be the product of the relatively prime

*n*, solve for some

_{i}*r*and

_{i}*s*such that

_{i}*r*= 1. This is solved with the extended Euclidean algorithm. Then let

_{i}n_{i}+ s_{i}N/n_{i}*e*, and the desired solution is the sum of the

_{i}= s_{i}N/n_{i}*a*. There will be multiple solutions, but they will all be congruent modulo

_{i}e_{i}*N*. If you get a number larger than this, take it modulo

*N*(which is 360360).

Or, if you can't figure out all that math, you could just write a program to iterate through the integers 1 to 360360 and print out the one where the equations are all true. It is 248447.

Having found this number by either method, you can now solve for the positions of the other gears by simply taking 248447 modulo the sizes of the gears.

- 248447 mod 29 = 4
- 248447 mod 17 = 9
- 248447 mod 22 = 1
- 248447 mod 20 = 7
- 248447 mod 28 = 3
- 248447 mod 16 = 15
- 248447 mod 19 = 3
- 248447 mod 26 = 17
- 248447 mod 23 = 1
- 248447 mod 27 = 20

Turning each gear this amount in the appropriate direction spells out **INTERLOCKS** on the letters marked at the top of each gear.