4

The question asks how many the divisions required to find $\gcd(34,55)$. I did it using the Euclidean Algorithm with the following result.

$$55=1 \cdot 34+21$$ $$34=1 \cdot 21+13$$ $$21=1 \cdot 13+8$$ $$13=1 \cdot 8+5$$ $$8=1 \cdot 5+3$$ $$5=1 \cdot 3+2$$ $$3=1 \cdot 2+1$$ $$2=2 \cdot 1+0$$ $$\gcd(34,55)=1$$

I wrote the answer $8$ since there are only $8$ steps needed, but the answer shown is $9$ divisions is required. I wonder if is the answer wrong or am I wrong?

Yuriy S
  • 31,474
J.Yang
  • 43
  • This is strange! Clearly, we need at most $8$ divisions – Peter Dec 05 '16 at 11:14
  • I hope this paper will give you a clear insight into the problem solving process. Hope it helps. –  Dec 05 '16 at 13:09
  • @YuriyS Thanks for your help! Is your answer same as the explanation in the answer sheet? "We need to divide successively by 55, 34, 21, 13, 8, 5, 3, 2, and 1, so 9 divisions are required." (Sorry I didn't put it in the question.) – J.Yang Dec 05 '16 at 13:24
  • @Rohan The paper you provided is about the LCM. Anyway thanks! – J.Yang Dec 05 '16 at 13:26
  • 1
    Two consecutive Fibonacci number is the "worst case" in the sense that it requires the most number of divisions.... The answer sheet says we need to divide by 1. Why bother? – DanielWainfleet Dec 05 '16 at 13:46
  • 1
    @Peter: Technically what J. Yang computed was $\gcd(55,34)$, but the Question was $\gcd(34,55)$. Doing things in that order (without picking the smalller number as divisor) adds a (wasted) step to the algorithm. – hardmath Dec 05 '16 at 15:49

3 Answers3

4

There is an uncertainty with finite continued fractions (which are a representation of the Euclidean algorithm). You can write:

$$\frac{34}{55}=\cfrac{1}{1+\cfrac{1}{1+\cfrac{1}{1+\cfrac{1}{1+\cfrac{1}{1+\cfrac{1}{1+\cfrac{1}{1+\cfrac{1}{2}}}}}}}}$$

Here we have $8$ 'levels' of the continued fraction.

On the other hand, we can write:

$$\frac{34}{55}=\cfrac{1}{1+\cfrac{1}{1+\cfrac{1}{1+\cfrac{1}{1+\cfrac{1}{1+\cfrac{1}{1+\cfrac{1}{1+\cfrac{1}{1+\cfrac{1}{1}}}}}}}}}$$

And now we have $9$ 'levels'.

We used the fact that $2=1+1=1+\frac{1}{1}$.

To be clear, for any rational number we have two equivalent continued fraction represenations.

By the way, this fraction is very close to the (reciprocal) Golden Ratio.

Yuriy S
  • 31,474
  • 1
    This is probably what is meant, but usually a trailing $1$ in a continued fraction (except [1]) is ruled out – Peter Dec 05 '16 at 11:51
  • 1
    The reason that $\frac{34}{55}\approx \frac{\sqrt{5}-1}{2}$ is that $34$ and $55$ are consecutive fibonacci numbers. For such fractions, the normal way to determine the gcd requires the most possible number of steps compared to the size of numerator and denominator of the fraction – Peter Dec 05 '16 at 12:00
  • 1
    @Peter, I agree. I also think that there are only 8 divisions, just as the OP did – Yuriy S Dec 05 '16 at 12:07
  • I understand the way you doing it and appreciate your help, but the only method we are allowed to use is the one I wrote. This is the explanation of the answer(Sorry I didn't put it in the question) :"We need to divide successively by 55, 34, 21, 13, 8, 5, 3, 2, and 1, so 9 divisions are required.". Any ideas? – J.Yang Dec 05 '16 at 13:22
  • 1
    @J.Yang, see my comment above (you've already read it). Dividing by $1$ is unconventional, but apparently your answer sheet thinks differently. That's alright – Yuriy S Dec 05 '16 at 13:32
  • This is a better suggestion than your comment on the Question, namely to consider what happens if we begin by trying to divide the smaller number $34$ by the larger $55$. That does waste a "division" step (and gets the larger divided by the smaller in the next step and following). – hardmath Dec 05 '16 at 15:40
2

The invariant in the Euclidean algorithm is that the gcd of consecutive numbers is constant. Thus your computations prove that

$$ (55,34) = (34,21) = (21,13) = (13,8) = (8,5) = (5,3) = (3,2) = (2,1) = (1,0)\ [ = 1]$$

using the normal convention the algorithm terminates when an argument is zero. Counting the number of gcds in the chain we get $\,9,\,$ not $\,8.\,$

Bill Dubuque
  • 272,048
  • 1
    Now we can have a substantive disagreement! I count eight steps above, and I believe the explanation for counting nine steps lies in the exact expression $\gcd(34,55)$ asked about. In other words the ninth step would be added at the beginning of your chain, $(34,55) = (55,34)$. – hardmath Dec 05 '16 at 16:20
  • @hardmath Disagreements about conventions are rarely fruitful. Best is to understand the innate concepts, which helps one to infer the ambient conventions in use. – Bill Dubuque Dec 05 '16 at 16:27
  • @hardmatjh And yes, what you wrote is another possible convention that may be in use. Hopefully from what is written here (and elsewhere) the OP has enough info to infer the ambient conventions. – Bill Dubuque Dec 05 '16 at 16:37
0

Your method is not bad but I think using lame's theorem is the best idea here. Lame theorem give an estimate of number of steps needed to find the greatest common divisor of two integers using Euclidian algorithm.

Vidyanshu Mishra
  • 10,143
  • The question is not to find the best method, but why we need $9$ divisions instead of $8$ – Peter Dec 05 '16 at 11:50