Obtaining certain pairs of numbers using three "machines"

Question

Each of three machines can read a card on which is written a pair of whole numbers $(m,n)$ and print a new card.

• Machine $\text{A}$ reads $(m,n)$ and prints $(m-n,n)$.
• Machine $\text{B}$ reads $(m,n)$ and prints $(m+n,n)$.
• Machine $\text{C}$ reads $(m,n)$ and prints $(n,m)$.

We are given a card $(19,81)$ in the beginning. Is it possible to obtain card $(a,b)$ using described machines finite many times, if (a) $a=7$, $b=13$; (b) $a=12$, $b=21$?

My attempt to solve this problem goes something like this.

First let's notice that we can never get a pair of even numbers with given pair $(19,81)$. Proof. Let's assume that, using these machines, we've gotten a pair of even numbers for the first time. In order to obtain the pair of even numbers, we must have had a pair of even numbers before. Since we are given two odd numbers, we can never get to pair of even numbers.

Now, we notice that using machines A or B, we change the parity of one number: $$ (o,o)\xrightarrow{A/B}(e,o)\quad\text{or}\quad(e,o)\xrightarrow{A/B}(o,o)\quad\text{or}\quad(o,e)\xrightarrow{A/B}(o,e). $$

We notice that having $AB$ (using machine A, then using machine B), $BA$ or $CC$ in sequence is pointless. So after each sequence of $A$'s or $B$'s has to end with $C$, after which we must place sequence of $A$'s or $B$'s again.

Also I tried experimenting by figuring out rules for modulo (for $7$, $13$, etc) but I couldn't figure it out either.

Also please note I'm looking for proof, not for the actual sequence of using machines. I don't have solution. Thanks.

Answer 1

Note that machine C is its self-inverse, an A and B are the inverse of each other, so we may start from (a) and (b) and try and get to $(19, 81)$.

In case (b), 12 and 21 are both divisible by 3, and this will hold for all pairs derived from them, so you can't get $(19, 81)$..

In case (a), note that using (a) and (c) you can run the Euclidean algorithm on $(7, 13)$ and get $(1, 0)$. Now using (b) and (c) you can run the Euclidean algorithm for $(81, 19)$ backwards and get $$ (1, 0)\ \textit{use (c) to get}\ (0,1)\ \textit{use (b) 4 times to get}\ (4,1)\ \textit{use (c) to get}\ (1,4)\ \textit{use (b) to get}\ (5, 4) \dots (81, 19) $$

Answer 2

I assume you are just learning about Euclid's algorithm, so I'll avoid referring to that. I'll just give some hints.

• Machines A and B are each others inverses, and C is its own inverse. Therefore if one can transform card X into Y, and can also transform Y into X
• Therefore if we can transform both X and Y into the same card Z, we can transform X and Y into each other.
• Show that you can always make a card of the form $(0,k)$. This is a good candidate for the target card Z.
• To show that two cards can never be transformed into each other, you need to find a property of the cards that none of the machines can change, and that distinguishes the two cards. Both numbers being even would be such a property, but you may need something more general.
• Using such a property, you may be abke to prove the card $(0,k)$ above is unique for any given initial card. You can then decide whether two cards are inter-convertible by transforming both into such a card.