# Euclidean algorithm for greatest common divisor

Using the euclidean algorithm for $\gcd(121, 330)$, how many divisions are required for the process?

-
Following Nike: "Just do it!" – Jyrki Lahtonen Feb 22 '13 at 20:05
There's no general formula to apply. Apparently you are expected to perform the Euclidean algorithm and count the number of division steps until a zero remainder is obtained. – hardmath Feb 22 '13 at 20:05
@user58512: There's an upper bound like that, but it doesn't give the exact number. – hardmath Feb 22 '13 at 20:09

Observe that \begin{align} \gcd(121,330) &= \gcd(121,88) \quad (88 = 330 - 2 \times 121.) \\ &= \gcd(33,88) \quad (33 = 121 - 1 \times 88.) \\ &= \gcd(33,22) \quad (22 = 88 - 2 \times 33.) \\ &= \gcd(11,22) \quad (11 = 33 - 1 \times 22.) \\ &= \gcd(11,0) = 11. \quad (0 = 22 - 2 \times 11.) \end{align} Therefore, $5$ steps are needed to terminate the Euclidean Algorithm for the pair $(121,330)$.

When applying the Euclidean Algorithm, the number of steps needed till termination never exceeds $5$ times the number of decimal digits in the smaller number. This fact is a consequence of Lamé’s Theorem. (Some authors label the fact itself as Lamé’s Theorem; see this link for an engaging discussion). The proof of the theorem, which can also be found in the preceding link, is interesting for its use of Fibonacci numbers.

-
That's not right! This result is a consequence of Lamé's theorem. Your own link spells this out. – TonyK Feb 22 '13 at 20:29
Some authors also call the initial result that I quoted as Lamé’s Theorem, but anyway, I have edited my post to reflect the content of the first link. :) Thanks! – Haskell Curry Feb 22 '13 at 21:58

This in Mathematica will give you the number of subtractions needed:

gcd[a_, b_] := gcd[Abs[a], Abs[b], 0];
gcd[a_, 0, step_] := {a, step};
gcd[0, b_, step_] := {b, step};
gcd[a_, b_, step_] := Which[
a >= b, gcd[a - b, b, step + 1],
b > a, gcd[a, b - a, step + 1]];


It's not optimized at all (it manually does each subtraction rather than using Mod) and probably what you want isn't the subtractions, but you can make modifications. It also shows you how you can make these kinds of "algorithmic" things in Mathematica by pattern matching. For example, the step in the algorithm that reads "if either number is 0, stop" is encoded in the 2nd and 3rd lines in the code.

A plot of the subtractions-required looks like this:

data = Table[gcd[i, j][[2]], {i, Range[0, 80]}, {j, Range[0, 80]}];
ListPlot3D[data, InterpolationOrder -> 2, Mesh -> None, Boxed -> False, PlotRange -> Full]


I know this is not exactly what you're looking for, but I wanted to bring in the computational perspective. :)

## Update

In response to @Jyrki's comment, here is the 'faster' version of the algorithm which subtracts as many multiples as possible in a given step:

gcd[a_, b_] := gcd[Abs[a], Abs[b], 0];
gcd[a_, 0, step_] := {a, step};
gcd[0, b_, step_] := {b, step};
gcd[a_, b_, step_] := Which[
a >= b, gcd[a - IntegerPart[a/b]*b, b, step + 1],
b > a, gcd[a, b - IntegerPart[b/a]*a, step + 1]];

data = Table[gcd[i, j][[2]], {i, Range[0, 599]}, {j, Range[0, 599]}];


Because the algorithm is fast (Max[data] shows that any two numbers between 0 and 599 will resolve in at most 12 steps), the value jumps rapidly between only a few discrete values (0-12), which makes a regular 3D plot very noisy. So I used a density plot instead:

ListDensityPlot[data, ImageSize -> {600, 600}, PlotRangePadding -> None, Frame -> None, Axes -> False]


Here's a "close-up" achieved by plotting in a different range:

data = Table[gcd[i, j][[2]], {i, Range[250949, 250949 + 599]}, {j, Range[0, 599]}];


-
But in Euclid's algorithm you always subtract the largest possible multiple of the smaller number in one step. It would be interesting to see that plot (IMHO upvote worthy). I would expect the golden ratio to show there. – Jyrki Lahtonen Feb 22 '13 at 21:55
I added some plots along those lines. I'm curious though why or in what way you expect the golden ratio to show itself (whether it's the case or not). – amr Feb 23 '13 at 5:13
+1: I expect the Golden ratio to show up, because $\gcd(F_n,F_{n+1})$ has the worst case complexity in Eucliden algorithm, so the lines with slopes $\phi^{\pm1}$ might be visible as high complexity regions. They sorta do, but not nearly as clearly as I hoped. – Jyrki Lahtonen Feb 23 '13 at 6:43
You might want to take a look at some results I've obtained with these density plots: math.stackexchange.com/questions/1579998/… Nice images, by the way! – Patryk Czachurski Jan 27 at 16:35

You don't need any divisions at all! You only need remainders, not quotients. As for how many remainders you need:

330/121 gives remainder 88
121/88 gives remainder 33

and so on. Stop when you get a remainder of 0 (and then the answer is the last non-zero remainder). It won't take you long :-)

-
how do you get the remainder without also getting the quotient in the process? – Jonathan Feb 22 '13 at 20:25
The process of finding the remainder is called " division with remainder". Then again, you could perform repeated subtraction "big minus small", but: then it's no longer Euklid's algorithm. – Hagen von Eitzen Feb 22 '13 at 20:34
@Jonathan, in general, you don't gain much by not having to compute the quotient. But you do gain a little $-$ if only because you are spared from having to actually store the quotient anywhere. Sometimes, however, it is much faster to compute a remainder than a quotient: in particular, when the numerator is much larger than the denominator. – TonyK Feb 22 '13 at 20:35
@Hagen: The process by which you find the remainder may well be called "division with remainder". But there are sometimes better ways. Rather trivially, if you are asked to compute 9748397356282374991 mod 7, you can just process a single digit at a time, and you won't have any idea at the end of it what the quotient is. – TonyK Feb 22 '13 at 20:40
@Hagen Huh? The ancient Euclidean algorithm uses ἀνθυφαίρεσις (anthyphairesis, reciprocal subtraction). For much more on the history see Fowler: The Mathematics of Plato's Academy – Math Gems Feb 22 '13 at 20:42