Register to reply 
Efficiency and the Euclidean Algorithm 
Share this thread: 
#1
Feb1011, 10:21 PM

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! :) 


#2
Feb1411, 07:41 AM

P: 273

Anyone?



#3
May912, 01:57 PM

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 r_{i}=q_{i+2}r_{i+1}+r_{i+2} and q_{i+2}≥1, you have r_{i}≥r_{i+1}+r_{i+2}. Then since r_{i+1}>r_{i+2}, you have r_{i}>r_{i+2}+r_{i+2}⇔r_{i}>2r_{i+2}⇔r_{i+2}<1/2r_{i}. 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. 


Register to reply 
Related Discussions  
Euclidean algorithm Proof  Linear & Abstract Algebra  1  
Euclidean algorithm  Calculus & Beyond Homework  3  
Euclidean algorithm  Set Theory, Logic, Probability, Statistics  2  
Euclidean algorithm  Calculus & Beyond Homework  4  
Euclidean algorithm  Linear & Abstract Algebra  1 