Register to reply

Efficiency and the Euclidean Algorithm

by Buri
Tags: algorithm, efficiency, euclidean
Share this thread:
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.


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
Wearable 4MM jetpack tested on speed, agility for runners (w/ Video)
How did evolution optimize circadian clocks?
Corn spots: Study finds important genes in defense response
Feb14-11, 07:41 AM
P: 273
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