On Lame's Theorem

Question

I was trying to study Lame's theorem but I'm a little bit stuck on one specific step... I write here the theorem and the proof:

Lame's theorem:
using the Euclidean algorithm to find the greatest common divisor of two positive integers has number of divisions less than or equal five times the number of decimal digits in the minimum of the two integers.

Proof:
Let $a$ and $b$ be two positive integers where $a > b$.
Applying the Euclidean algorithm to find the greatest common divisor of two integers with $a = r_{0}$ and $b = r_{1}$, we get
$r_{0} = r_{1}q_{1}+r_{2}$, $0≤r_{2}<r_{1}, $
$r_{1} = r_{2}q_{2}+r_{3}$, $0≤r_{3}<r_{2}, $
. . .
$r_{n-2} = r_{n-1}q_{n-1}+r_{n}$, $0≤r_{n}<r_{n-1}, $
$r_{n-1} = r_{n}q_{n}$

Notice that each of the quotients $q_{1}, q_{2}, ..., q_{n-1} $ are all greater than $1$ and $q_{n} ≥ 2$ and this is because $r_{n} < r_{n-1}.$

Thus we have

$r_{n} ≥ 1=f_{2}$,
$r_{n-1} ≥ 2r_{n} ≥ 2f_{2} = f_{3}$,
$r_{n-2} ≥ r_{n-1} + r_{n} ≥ f_{3} + f_{2} = f_{4}$,
$r_{n-3} ≥ r_{n-2} + r_{n-1} ≥ f_{4} + f_{3} = f_{5}$,
...
$r_{2} ≥ r_{3} + r_{4} ≥ f_{n-1} + f_{n-2} = f_{n}$,
$b = r_{1} ≥ r_{2} + r_{3} ≥ f_{n} + f_{n-1} = f_{n+1}$.

Thus notice that $b≥f_{n+1}$. By a Lemma I don't report here, we have $f_{n+1}>α^{n−1}$ for $n>2$. As a result, we have $b > α^{n−1}$.

Now notice since $\log_{10} \alpha > \frac{1}{5}$

we see that

$\log_{10}b > (n − 1)/5$.

Thus we have

$(n - 1)< 5 log_{10}b$

Now let $b$ has $k$ decimal digits. As a result, we have $b < 10^k$ and thus $log_{10}b < k$. Hence we conclude that $(n − 1) < 5k$.
Since $k$ is an integer, we conclude that $n ≤ 5k$.

What I really don't understand is just this line:

Now notice since $\log_{10} \alpha > \frac{1}{5}$,

My question is: why $\frac{1}{5}$ has been chosen?

Where does it come from? Has it been chosen because the theorem says:

[...]less than or equal five times [...] ?

Thank you

Answer 1

Let's chase through the rest of the proof without using the line $\log_{10}\alpha>1/5$. So instead of writing $\log_{10}b>(n-1)/5$, we'll just write $$\log_{10}b>(n-1)\log_{10}\alpha.$$ Continuing through the rest of the algebra, we end up with $$n-1<k/\log_{10}\alpha.$$

So, this actually gives a more precise conclusion to the theorem: the number of steps $n$ is less than $1$ plus the number of decimal digits $k$ times the constant $C=1/\log_{10}\alpha$. If we now observe that $\log_{10}\alpha>1/5$ so $C<5$, we can conclude that $n$ is at most the number of decimal digits times $5$, which is the originally stated (but weaker) conclusion. It is natural to choose $5$ here since it is the smallest integer greater than $C$.

Answer 2

You can easily expand out the polynomial $({1+\sqrt{5}})^{5}$ and confirm it is greater than $10*2^{5}$

Answer 3

You can play around with things a bit too.

Given $\alpha=\dfrac{1+\sqrt{5}}{2}$, it follows that

\begin{align} \alpha^2 &= \alpha + 1 \\ \alpha^3 &= \alpha^2 + \alpha \\ &= 2\alpha + 1 \\ \alpha^4 &= 2\alpha^2 + \alpha \\ &= 3\alpha + 2 \\ \alpha^5 &= 3\alpha^2 + 2\alpha \\ &= 5\alpha + 3 \\ &> \dfrac{5+10}{2}+3 &\text{Since $\sqrt 5 >2.$} \\ &> 10 \end{align}

So $\alpha^5 > 10 \implies 5 \log_{10}\alpha > 1 \implies \log_{10}\alpha > \dfrac 15.$

A lot of problems can be solved by assuming that what you find out is useful and then going on to see what happens. He probably chose $\dfrac 15$ because he found, using whatever method, that $\log_{10} \alpha > \dfrac 15$. He then just assumed that that was useful information and proceeded with the rest of the proof. If faith isn't a good enough reason, then just follow through out of curiosity to see what happens. Even if you fail, you now know more that you did before.