Efficiency and the Euclidean Algorithm

In summary, the Euclidean algorithm applied to a and b reduces the remainder by at least one half in every two steps, as shown by the inequality ri+2<(1/2)ri for every i=0,1,2,...
  • #1
Buri
273
0
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:
Physics news on Phys.org
  • #2
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:

1. What is the Euclidean Algorithm?

The Euclidean Algorithm is an efficient method for finding the greatest common divisor (GCD) of two integers. It was developed by the ancient Greek mathematician Euclid and is based on the principle that the GCD of two numbers is the same as the GCD of the smaller number and the difference between the two numbers.

2. How does the Euclidean Algorithm work?

The Euclidean Algorithm works by repeatedly dividing the larger number by the smaller number and taking the remainder. This process is repeated until the remainder is equal to 0. The last non-zero remainder is the GCD of the two numbers.

3. Why is the Euclidean Algorithm efficient?

The Euclidean Algorithm is efficient because it reduces the number of calculations needed to find the GCD. It only requires simple division and subtraction operations, which can be performed quickly by a computer.

4. What is the relationship between the Euclidean Algorithm and the concept of efficiency?

The Euclidean Algorithm is an example of an efficient algorithm. It is designed to minimize the number of operations required to solve a problem, making it a useful tool for solving mathematical problems in an efficient manner.

5. How is the Euclidean Algorithm used in real-world applications?

The Euclidean Algorithm has many practical applications, such as in cryptography, computer graphics, and error-correcting codes. It is also used in various fields of science, including physics, chemistry, and biology, to solve problems involving ratios, proportions, and scaling.

Similar threads

  • General Math
Replies
4
Views
3K
  • Classical Physics
Replies
4
Views
214
  • Advanced Physics Homework Help
Replies
11
Views
1K
  • Calculus and Beyond Homework Help
Replies
5
Views
2K
  • Calculus and Beyond Homework Help
Replies
5
Views
1K
  • Differential Geometry
Replies
1
Views
1K
  • Linear and Abstract Algebra
Replies
2
Views
1K
Replies
1
Views
897
  • Advanced Physics Homework Help
Replies
6
Views
1K
Back
Top