Register to reply

Efficiency and the Euclidean Algorithm

by Buri
Tags: algorithm, efficiency, euclidean
Share this thread:
Buri
#1
Feb10-11, 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! :)
Phys.Org News Partner Science news on Phys.org
Hoverbike drone project for air transport takes off
Earlier Stone Age artifacts found in Northern Cape of South Africa
Study reveals new characteristics of complex oxide surfaces
Buri
#2
Feb14-11, 07:41 AM
P: 273
Anyone?
elliesmall
#3
May9-12, 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 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.


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