# Efficiency and the Euclidean Algorithm

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

Last edited: