# Euclidean algorithm

• Jan 17th 2010, 11:54 PM
kingwinner
Euclidean algorithm

All I think can of is the following:
Since the reaminder become strictly smaller each step, the worst case is when the remainders go down by 1 each step, in which case the process will take "b" steps in total to complete. Therefore, the process will terminate in at most "b" steps.

But how can we prove that all reaminders satisfy the inequality r(i+2) < r(i)/2? By induction? or...? This seems to provide a much better upper bound on the number of steps to complete the process.

Any help is much appreciated!

[also under discussion in s.o.s. math board]
• Jan 18th 2010, 04:43 PM
Bruno J.
Well you have \$\displaystyle r_i = r_{i+1}q_{i+2}+r_{i+2}\$. So \$\displaystyle r_i-2r_{i+2} = r_{i+1}q_{i+2}-r_{i+2}\$. Since \$\displaystyle q_{i+2}\geq 1\$ and \$\displaystyle 0<r_{i+1}<r_{i+2}\$ you have \$\displaystyle r_i-2r_{i+2} = r_{i+1}q_{i+2}-r_{i+2} \geq r_{i+1}-r_{i+2} > 0\$.
• Jan 19th 2010, 09:58 AM
kingwinner
Quote:

Originally Posted by Bruno J.
Well you have \$\displaystyle r_i = r_{i+1}q_{i+2}+r_{i+2}\$. So \$\displaystyle r_i-2r_{i+2} = r_{i+1}q_{i+2}-r_{i+2}\$. Since \$\displaystyle q_{i+2}\geq 1\$ and \$\displaystyle 0<r_{i+1}<r_{i+2}\$ you have \$\displaystyle r_i-2r_{i+2} = r_{i+1}q_{i+2}-r_{i+2} \geq r_{i+1}-r_{i+2} > 0\$.

But I think q(i+2) can be 0?

Also, I think we should have 0<r(i+2)<r(i+1)?

thanks.
• Jan 19th 2010, 11:13 AM
Jhevon
Quote:

Originally Posted by kingwinner
But I think q(i+2) can be 0?

Remember, \$\displaystyle r_i \ge r_{i + 1}\$ (if equal, the algorithm only has one step). If the algorithm starts with \$\displaystyle r_{i + 1} > r_i\$, then they are switched in the very next line. So, if our algorithm is to have more than one line, it is just assumed that \$\displaystyle r_i > r_{i + 1}\$ right off the bat. In this case, \$\displaystyle q_{i + 2} \ge 1\$ is forced to happen.

Quote:

Also, I think we should have \$\displaystyle 0 < r_{i + 2} < r_{i + 1}\$?
yes, BrunoJ had a typo. But if you look at what he did, you can see that he assumed just as you wrote here.