Originally Posted by

**dashed** I don't know whether I posted in the proper forum.

This is a question from a 2009 grade 9 math competition.

The question

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 + 3n, n).

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

Natalie starts with a 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)

**B.** (2009, 1004)

**C.** (2009, 1002)

**D.** (2009, 1008)

**E.** (2009, 1032)

A friend have found D to be suspicious through methods of brute force.

I looked at the problem for a while, and I've been unable to find a solution.

Can someone provide insight as to how to solve this particular problem?