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
Experts defend operational earthquake forecasting, counter critiques
EU urged to convert TV frequencies to mobile broadband
Sierra Nevada freshwater runoff could drop 26 percent by 2100
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