Starting with the input $(m, n)$, Machine A gives the output $(n, m)$.

Starting with the input $(m, n)$, Machine B gives the output $(m+3 n, n)$.

Starting with the input $(m, n)$, Machine C gives the output $(m-2 n, n)$.

Natalie starts with the pair $(0,1)$ and inputs it into one of the machines. She takes the output and inputs it into any one of the machines. She continues to take the output that she receives and inputs it into any one of the machines. (For example, starting with $(0,1)$, she could use machines B, B, A, C, B in that order to obtain the output $(7,6)$.) Which of the following pairs is impossible for her to obtain after repeating this process any number of times?
(A) $(2009,1016)$
(D) $(2009,1008)$
(B) $(2009,1004)$
(E) $(2009,1032)$
(C) $(2009,1002)$
The three machines operate in a way such that if the two numbers in the output have a common factor larger than 1, then the two numbers in the input would have to have a common factor larger than 1.

To see this, let us look at each machine separately. We use the fact that if two numbers are each multiples of $d$, then their sum and difference are also multiples of $d$.

Suppose that $(m, n)$ is input into Machine A. The output is $(n, m)$. If $n$ and $m$ have a common factor larger than 1 , then $m$ and $n$ do as well.

Suppose that $(m, n)$ is input into Machine B. The output is $(m+3 n, n)$. If $m+3 n$ and $n$ have a common factor $d$, then $(m+3 n)-n-n-n=m$ has a factor of $d$ as each part of the subtraction is a multiple of $d$. Therefore, $m$ and $n$ have a common factor of $d$.

Suppose that $(m, n)$ is input into Machine C. The output is $(m-2 n, n)$. If $m-2 n$ and $n$ have a common factor $d$, then $(m-2 n)+n+n=m$ has a factor of $d$ as each part of the addition is a multiple of $d$. Therefore, $m$ and $n$ have a common factor of $d$.

In each case, any common factor that exists in the output is present in the input.

Let us look at the numbers in the five candidates.

After some work, we can find the prime factorizations of the six integers:

$$
\begin{aligned}
& 2009=7(287)=7(7)(41) \\
& 1016=8(127)=2(2)(2)(127) \\
& 1004=4(251)=2(2)(251) \\
& 1002=2(501)=2(3)(167) \\
& 1008=8(126)=8(3)(42)=16(3)(3)(7)=2(2)(2)(2)(3)(3)(7) \\
& 1032=8(129)=8(3)(43)=2(2)(2)(3)(43)
\end{aligned}
$$

Therefore, the only one of 1002, 1004, 1008, 1016, 1032 that has a common factor larger than 1 with 2009 is 1008, which has a common factor of 7 with 2009.

How does this help? Since 2009 and 1008 have a common factor of 7, then whatever pair was input to produce $(2009,1008)$ must have also had a common factor of 7 . Also, the pair that was input to create this pair also had a common factor of 7 . This can be traced back through every step to say that the initial pair that produces the eventual output of $(2009,1008)$ must have a common factor of 7 .

Thus, $(2009,1008)$ cannot have come from $(0,1)$.

Notes:

- This does not tell us that the other four pairs necessarily work. It does tell us, though, that $(2009,1008)$ cannot work.
- We can trace the other four outputs back to $(0,1)$ with some effort. (This process is easier to do than it is to describe!)

To do this, we notice that if the output of Machine A was $(a, b)$, then its input was $(b, a)$, since Machine A switches the two entries.

Also, if the output of Machine B was $(a, b)$, then its input was $(a-3 b, b)$, since Machine $\mathrm{B}$ adds three times the second number to the first.

Lastly, if the output of Machine C was $(a, b)$, then its input was $(a+2 b, b)$, since Machine C subtracts two times the second number from the first.

Consider $(2009,1016)$ for example. We try to find a way from $(2009,1016)$ back to $(0,1)$. We only need to find one way that works, rather than looking for a specific way.

We note before doing this that starting with an input of $(m, n)$ and then applying Machine $\mathrm{B}$ then Machine $\mathrm{C}$ gives an output of $((m+3 n)-2 n, n)=(m+n, n)$. Thus, if applying Machine B then Machine C (we call this combination "Machine BC") gives an output of $(a, b)$, then its input must have been $(a-b, b)$. We can use this combined machine to try to work backwards and arrive at $(0,1)$. This will simplify the process and help us avoid negative numbers.

We do this by making a chart and by attempting to make the larger number smaller wherever possible:

| Output | Machine | Input |
| :---: | :---: | :---: |
| $(2009,1016)$ | $\mathrm{BC}$ | $(993,1016)$ |
| $(993,1016)$ | $\mathrm{A}$ | $(1016,993)$ |
| $(1016,993)$ | $\mathrm{BC}$ | $(23,993)$ |
| $(23,993)$ | $\mathrm{A}$ | $(993,23)$ |
| $(993,23)$ | $\mathrm{BC}, 43$ times | $(4,23)$ |
| $(4,23)$ | $\mathrm{A}$ | $(23,4)$ |
| $(23,4)$ | $\mathrm{BC}, 5$ times | $(3,4)$ |
| $(3,4)$ | $\mathrm{A}$ | $(4,3)$ |
| $(4,3)$ | $\mathrm{BC}$ | $(1,3)$ |
| $(1,3)$ | $\mathrm{A}$ | $(3,1)$ |
| $(3,1)$ | $\mathrm{B}$ | $(0,1)$ |

Therefore, by going up through this table, we can see a way to get from an initial input of $(0,1)$ to a final output of $(2009,1016)$.

In a similar way, we can show that we can obtain final outputs of each of $(2009,1004)$, $(2009,1002)$, and $(2009,1032)$.