Problem: I am currently standing on the number line at the number 0, and I am allowed to make two types of moves. Firstly, I can move 17 to the right or left. Secondly, I can move 41 to the right or left. So, which positive integers on the number line can be reached using these two moves.

Solution: All positive integers can be reached using these two moves. To see this, first notice that we can reach the positive integer n given that n is a linear combination of 17 and 41, meaning that n = 17a + 41b for some integers a and b. Now, consider the tuple of positive integers (17, 41). It is trivial to see that both 17 and 41 can be reached to using the moves specified in the problem. Now we create a sequence of such tuples with the rule being that if the current term is (a, b), with a >= b, then the next term will be (a – b, b). (Note that the tuples considered are unordered, i.e. The order of the elements in the tuple does not matter)

Note that each positive integer in every tuple of this sequence can be reached using the two moves given in the problem statement! This can simply be proven using induction. As mentioned earlier, it is obvious that 17 and 41 can be reached, so the basis case is trivial. Now if I know that I can reach a and b using these moves, then a and b are linear combinations of the integers 17 and 41, so their difference is also a linear combination of the integers 17 and 41, so I can also reach a – b and b using the two moves, hence proving the inductive step. Therefore, the statement given in the beginning of this paragraph is true.

Now, we must consider what numbers actually appear in this sequence of tuples. Firstly, let’s find an invariant in this sequence of tuples. Note that the greatest common divisor of the pair of numbers in the tuple is the same for all tuples in the sequence. To see this, note that if d is a divisor of a and b, then it is also a divisor of a – b. Similarly, if d is a divisor of a – b and b, then it is also a divisor of a – b + b = a. So d is a common divisor for the first tuple if and only if it is a common divisor for the second tuple. So the set of common divisors for both of the tuples are identical, and since these sets are identical, the greatest elements of the sets are also identical, and the greatest elements of these sets are nothing but the greatest common divisors. So every tuple will have the same greatest common divisor of its two elements, so the first tuple will have the same greatest common divisor as the last tuple.

Note that the greatest common divisor of 17 and 41 (The first tuple) is 1. There can never be a negative number in these tuples, because the smaller number is always subtracted from the larger number, so the sequence only ends when one number becomes 0. Since 0 is divisible by all positive integers, and the greatest common divisor of the last tuple is 1, the second element of the last tuple must be 1. Since 1 appears in the last tuple, it is possible to reach the number 1 using these two moves. Hence it is possible to move 1 to the right, and since all positive integers can be reached through a series moves of length 1 to the right, all positive integers can be reached using the two moves, as desired.

To generalise this argument by replacing 17 and 41 with arbitrary positive integers a and b, it is not hard to see that the positive integers which can be reached using the two moves are those positive integers which are multiples of the greatest common divisor of a and b. This can easily be seen by replacing 17 and 41 with the arbitrary positive integers a and b in the argument above. In fact, this is a very well known fact in number theory which follows from Euclid’s Division Algorithm.

Don’t forget to check my blog next week for another fascinating problem!!