# Remainders of Euclid's algorithm

Let $$b_0,b_1,b_2$$,... be the successive remainders computed in the course of Euclid’s algorithm. Prove that $$b_{i+2} < b_{i}/2$$ for any i ≥ 1.

So we know that $$b_i > b_{i+1} > b_{i+2}$$ for every i, and $$b_i = kb_{i+1} + b_{i+2}$$, for integer $$k\geq 1$$, so $$b_i > (k+1)b_{i+2} \geq 2b_{i+2}$$, which leads us to the desired result.

Is my proof correct? Now the lecturer proposed that we take two cases, namely $$b_{i+1} =< b_{i}/2$$ and $$b_{i+1} > b_{i}/2$$, but i was struggling to prove the result in the second case, so i took this alternative route.

• Looks correct to me. – darij grinberg Feb 17 '19 at 17:02
• @darijgrinberg Thank god, but for future reference, do you know how to prove the 2nd case of the proposed solution? – user600210 Feb 17 '19 at 17:08
• I'd just say it contradicts $b_i \geq 2b_{i+2}$ and thus cannot occur. – darij grinberg Feb 17 '19 at 17:10
• math.stackexchange.com/questions/1835592/…, math.stackexchange.com/questions/2420259/… both present a proof of the 2nd case, but I cannot bring my head to understand it... but it seems like it's not a contradiction and you can actually prove it – user600210 Feb 17 '19 at 17:16
• Note that Lance's proof distinguishes cases based upon the relation between $b_{i+1}$ and $b_{i+2}$, not between $b_i$ and $b_{i+2}$. Not sure what TheLast is doing. – darij grinberg Feb 17 '19 at 17:20