# Efficiency and the Euclidean Algorithm

by Buri
Tags: algorithm, efficiency, euclidean
 P: 273 1. Question Let b = r_0, r_1, r_2,... be the successive remainders in the Euclidean algorithm applied to a and b. Show that every two steps reduces the remainder by at least one half. In other words, verify that r_(i+2) < (1/2)r_i for every i = 0,1,2,... 2. Attempt at a solution I take an arbitrary 'line' in the euclidean algorithm which is of the following form: r_i = q_(i+2) x r_(i+1) + r_(i + 2) So clearly I have the following: 1 > r_(i+2) / r_(i+1), because r_0 > r_1 > r_2 ... Now q_(i+2) >= 1. So we have: q_(i+2) > r_(i+2) / r_(i+1) Which implies: q_(i+2) x r_(i+1) > r_(i+2) q_(i+2) x r_(i+1) + r_(i+2) > 2r_(i+2) But q_(i+2) x r_(i+1) + r_(i+2) = r_i. Thus, r_i > 2r_(i+2) which is what I wanted to prove. 3. Comments However, I see possible problems with this proof. To begin with, the Euclidean Algorithm I am working with doesn't explicitly state that a > 0 or b > 0, but in this question it seems to be implicitly be saying that b > 0 (and says nothing of a) because b = r_0 which must be greater than 0. But if a were negative and b positive I could have a q which is not necessarily positive (more specifically, not greater or equal to 1) which would mess up my proof. But since it seems to be that b > 0 then q's will always be strictly greater than 1, even though it could be possible that the first q could turn out to be negative (for example in, a = -9 and b = 4 in which case q = -3 and r = 3). See what I mean? I would prefer if people could help me sort this proof out rather than give me ideas of how to go about it differently. I'd appreciate the help! :)
 P: 273 Anyone?
 P: 1 I know you asked for people not to give you a different method. However, it seems to me you're doing a lot more work than you need to. Since ri=qi+2ri+1+ri+2 and qi+2≥1, you have ri≥ri+1+ri+2. Then since ri+1>ri+2, you have ri>ri+2+ri+2⇔ri>2ri+2⇔ri+2<1/2ri. Further, since gcd(a,b)=gcd(-a,b)=gcd(a,-b)=gcd(-a,-b), you may use the absolute values of a and b while using the algorithm, ensuring that every q is always greater or equal to 1.

 Related Discussions Linear & Abstract Algebra 1 Calculus & Beyond Homework 3 Set Theory, Logic, Probability, Statistics 2 Calculus & Beyond Homework 4 Linear & Abstract Algebra 1