# How is the process of reducing the fraction down to zero almost exactly the same as finding the greatest common divisor?

Professor Sir Tom Davis in a note - Conway's Rational Tangles has said $$\\$$ If the students are a bit advanced, you can point out that the process of reducing the fraction down to zero is almost exactly the same as finding the greatest common divisor (the GCD) of the numerator and denominator. $$\\$$.

I understand the Euclidean algorithm to find gcd and the rational tangle algorithm but cannot translate the steps of Euclidean algorithms in terms of rational tangles algorithm.

I was trying to understand with an example, with two number $$19$$ and $$11$$.

To find the gcd we follow the steps:-

$$19 = 11.1+8\\11 = 8.1 + 3\\8 = 3.2 + 2\\3 = 2.1 + 1\\2 = 1.2+0$$

where gcd is $$1$$.

Now using rational tangle algorithm we have, $$\frac{19}{11}{\longrightarrow}^{R}\longrightarrow \frac{-11}{19}{\longrightarrow}^{T}\longrightarrow \frac{8}{19}{\longrightarrow}^{R}\longrightarrow \frac{-19}{8}{\longrightarrow}^{T^3}\longrightarrow \frac{5}{8}{\longrightarrow}^{R}\longrightarrow \frac{-8}{5}{\longrightarrow}^{T^2}\longrightarrow \frac{2}{5}{\longrightarrow}^{R}\longrightarrow \frac{-5}{2}{\longrightarrow}^{T^3}\longrightarrow \frac{1}{2}{\longrightarrow}^{R}\longrightarrow -2{\longrightarrow}^{T^2}\longrightarrow0$$

where $$T=x+1, \ R=\frac{-1}{x}$$ and $$x$$ is initial stage before any twist or rotation and $$T^n$$ denotes $$n$$ times twists.

In both algorithms, we see $$0$$ at the final step but the gcd in Euclidean algorithm is $$1$$ and according to the rational tangle algorithm the total number of attempts to make $$0$$ tangles is $$-1+1-1+3-1+2-1+3-1+2=6$$ which is greater than $$1$$.

1.Then how the process of reducing the fraction down to zero is almost exactly the same as finding the greatest common divisor? $$\\$$ 2. Is it correct to assume the multiplication of divisor and quotient as rotation and the remainder as twist?

• Okay. I think I understand. The only difference is that you can use the process to answer two different questions. For example. If I gave you a method of keeping track of what you fed an elephant and I said "Now count the number of meals and divide by 2" that tells you how long the elephant lives. And then "Now add up the meals" that tells you how much an elephant eats in its life. They both use the same method "write down the meals" but they answer two different questions. – fleablood Mar 14 at 18:40
• In both you are doing the same thing. But to find the gcd you are only keeping track of the remainder. You don't care about the coeficients; the the rational triangle you don't care about the remainder you only keep track of the coefficient. Same method; different aspect; different answers. – fleablood Mar 14 at 18:43
• @fleablood, This is helpful. Thank you. – thevbm Mar 14 at 18:44
• Bear in mind I haven't seen much of the rational tangle theorem so I'm mostly guessing how it works. But what you are doing--Finding quotient and remainder of a divisor and number, and then repeat but with the divisor as the new number and the remainder as the new divisor-- is clearly the same in both. – fleablood Mar 14 at 18:47