Exploring the Euclidean Algorithm with Mathematica

We can easily implement the Euclidean Algorithm in Mathematica, by appealing to the recursive relationship at its heart. Perhaps the shortest way to do this would be with the following:

 g[x_,y_] := Which[ Mod[x,y] == 0, y, True, g[y,Mod[x,y]] ]

A natural point of curiosity would be to wonder about how many steps the Euclidean Algorithm takes for a given pair of integers. As a slight variation, one might wonder what is the "smallest" pair of numbers that produces $n$ steps.

Note, with a slight modification the formula above can easily keep track of how many steps the Euclidean Algorithm takes to find the gcd of two numbers:

 g[x_,y_,c_] := Which[ Mod[x,y] == 0, {y, c+1}, True, g[y, Mod[x,y], c+1] ]

Here's an example of how to call this "modified" function:
 
 g[1160718174, 316258250, 0]
 
 results in 
 
 {1078, 10}
 
 which tells us that the Euclidean Algorithm took 10 steps to find the gcd of 1078.

Now, to be organized in our hunt for something interesting about the number of steps needed, we might create a table of how many steps various pairs of values need in the Euclidean Algorithm as one computes their gcd.

This again, can easily be done in Mathematica with the following additional code:

TableBody = Table[Table[Part[g[i, j, 0], 2], {i, 35}], {j, 35}];
ColHeadersAdded = Prepend[TableBody, Table[n, {n, 35}]];
RowHeadersAdded = Grid[MapThread[Prepend, {ColHeadersAdded, Table[m - 1, {m, 36}]}]]

Running the above, we produce the following:

Notice the smallest positive integer $a$ for which there is a smaller number $b$ so that the Euclidean algorithm applied to $a$ and $b$ stops in $n$ steps is the $(n+2)$nd Fibonacci number. Further, the corresponding $b$ is the $(n+1)$st Fibonacci number.

Isn't that interesting! This result is known as Lame's Theorem -- named after Gabriel Lame, a french mathematician in the 1800's.