Efficiency and the Euclidean Algorithm

  • Thread starter Buri
  • Start date
  • #1
273
0

Main Question or Discussion Point

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

Answers and Replies

  • #2
273
0
Anyone?
 
  • #3
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.
 
Last edited:

Related Threads on Efficiency and the Euclidean Algorithm

  • Last Post
Replies
1
Views
4K
  • Last Post
Replies
1
Views
3K
  • Last Post
Replies
1
Views
6K
  • Last Post
Replies
4
Views
3K
Replies
6
Views
3K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
8
Views
4K
  • Last Post
Replies
1
Views
4K
Top