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.

  • $\begingroup$ Looks correct to me. $\endgroup$ – darij grinberg Feb 17 at 17:02
  • $\begingroup$ @darijgrinberg Thank god, but for future reference, do you know how to prove the 2nd case of the proposed solution? $\endgroup$ – JBuck Feb 17 at 17:08
  • $\begingroup$ I'd just say it contradicts $b_i \geq 2b_{i+2}$ and thus cannot occur. $\endgroup$ – darij grinberg Feb 17 at 17:10
  • $\begingroup$ 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 $\endgroup$ – JBuck Feb 17 at 17:16
  • $\begingroup$ 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. $\endgroup$ – darij grinberg Feb 17 at 17:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.