Euclid and Fibonacci and the Eiffel Tower

Gabriel Lame, the French Mathematician (the capital M is intentional, he was) is very little known to most teachers and students, certainly at the high school level.  Which makes it all the more surprising that his name and work keeps showing up lately on my twitter feed.

For instance someone wrote recently about the "squircle", supposedly a cross between a square and a circle. Honest. (My first thought... why a new name, it has a perfectly good one, named for Gabriel Lame.)
  There is even a link to it on Mathworld.  But even they don't mention my boy Gabe.  The term is now usually applied to a roundish shape \( x^4 + y^4 = r^4 \) (you can see the relation to the circle formula) although the term squircle was created for a similar looking shape with a much more complex formula, by Fernández Guasti in 2005.

But the Mathworld article does mention the Super-Ellipse, a name coined by  Danish poet, designer, mathematician, inventor and scientist (I probably left some stuff out) Piet Hein, around 1959, for a traffic circle. Only he didn't mean the squircle, His design used the 5/2 power and his was taller than wide, so more of a (forgive me Math Gods) "rectircle" than squircle, Later he rotated that same figure to create (and name) the Super egg which was a novelty for a while also. It was an egg shaped object, but it would balance on one end. 
"Superellipse" caught on. Martin Gardner wrote about it ( (1977), "Piet Hein’s Superellipse", Mathematical Carnival. A New Round-Up of Tantalizers and Puzzles from Scientific American,) and he had a lot more readers than Lame, and so his term was soon generalized to equations of the form \( | (\frac{x}{a})^n | +  | (\frac{y}{b})^n | =1  \).  And if you look up the term Lame curve in Wikipexdia, it takes you to "SUPERELLIPSE"  which begins, "A superellipse, also known as a Lamé curve..."  which Lame wrote about in 1818 so as you can see, Gabriel just doesn't get much respect. 

Ok, but so far, no Euclid, No Fibonacci, and no Eiffel Tower... (patience my reader)...

A few days later I was diverted, as I sometimes am, by something in Alexander Bogomolny's Cut the Knot web site, because he mentioned Lame's Theorem.  If you follow that link, be warned; you can sink into this site and not be seen for days.
Alex's article was titled "Lamé's Theorem - the Very First Application of Fibonacci Numbers." Which got me curious. The Lame's Theorem I knew had to do with the Euclidean algorithm for finding greatest common factors.  Sure enough that was the one he meant.
Now what Lame said (1844), at least as far as I know, is that if you use the Euclidean Algortihm, it will only take a finite time to work, in fact he said it would take no more than five times the number of digits in the decimal number which was the smaller of the two.  So if you have 13502 and 235, at the most it will take 5*3 or 15 iterations of the algorithm.  (go ahead, if you want to test that, I'll wait..)

But Alex added another theorem by Donal Knuth (1969) pointed out that of all the numbers \( x>y \) that take exactly n steps to execute, if you found the pair with the smallest y , then y = Fib_n+2 and x = Fib_n+1 .  
Ok, a little hand waving talk::: If we take two numbers and it takes six iterations of the algorithm to get to zero, then the larger of the two numbers we used must be greater than F₈, or 21.
What that Doesn't mean, is that if you take a larger number, it will take more than six iterations.  For example, finding the greatest common factor of 34 and 8, it only takes two steps ( 34 Mod 8 = 2; 8 mod 2 = 0).  What it does say is that there is a smaller pair that only takes two steps, F₄ and FF₃ , the pair 3,2.
I really had to wrap my head around why the smallest pair with n iterations would be a Fibonacci pair, and it was related to the original way that Euclid defined his rule in The Elements, Book VII, prop. 1, "When two unequal numbers are set out, and the less is continually subtracted in turn from the greater, if the number which is left never measures the one before it until a unit is left, then the original numbers are relatively prime." It works by subtraction... he even used the Greek term, "antenaresis", which I am told means "repeated subtraction."
When we use the algorithm in practice, we take advantage of modular arithmetic to take care of subtracting lots of smaller numbers from the larger, if possible. For instance, in 34 and 8, if we used repeated subtraction, we would keep subtracting 8 from 34 until we got a residue of less than 8, but our modular process does this in one step. 8 and 34 have the same common divisor as 8,26; 8,18; and 8,10, they all leave a residue of 2.
Imagine each variable with a unique name, with a as bigger and b,c,d,e getting progressively smaller. Our algorithm would lead, step by step to
a mod b = c; b mod c = d, c mod d = e... etc.
Now what if we start with e as a known? Because we subtracted, at least, d we know that:
c >= d+e
b >= c+d = (d+e) + d = 2d+e;
a >= b+c = (c+d)+(d+e) = (2d+e)+ (d+e) = 3d+2e,

Looks familiar, doesn't it, so if we let d and e be one, then we produce the smallest number you can reach in n steps of the algorithm. you might reach a bigger number, but no smaller than F_n+2.

The Cut-The-Knot link above has a nice proof that may be something of a stretch for HS students, so I hope they can follow my shallower explanation. It also plots of pairs that take n steps on a coordinate grid.

Oh, and the Eiffel Tower!... If you visit Paris and go to the Tower, Look up around the borders of the four sides of the tower, and you will see the names of 72 scientist's that Eiffel felt worthy of homage, one of them is Gabriel Lame.