Why does +bc become negative in the proof of the Euclidian Algorithm?

  • I
  • Thread starter MienTommy
  • Start date
  • Tags
    Algorithm
In summary, the Euclidian Algorithm is a mathematical method for finding the greatest common divisor of two or more numbers. It is efficient and can be used for various types of numbers, including integers, rational numbers, and complex numbers. It is proved using mathematical induction and can be extended to find the GCD of multiple numbers.
  • #1
MienTommy
22
0


In this video, at 5:35 He has d/(a-qb) for the first part. I was not sure how he got that. Why is it not d/(a+qb)?

Because d/a and d/bc implies d/(a+bc)

Why does +bc become negative?
 
Mathematics news on Phys.org
  • #2
It divides both.

If a=x*d and b=y*d then a-qb=x*d - q*y*d = (x-qy)*d and also a+qb=x*d + q*y*d = (x+qy)*d
The second formula less useful for the next step, however, because it would make numbers larger.
 

1. What is the Euclidian Algorithm?

The Euclidian Algorithm is a mathematical method for finding the greatest common divisor (GCD) of two numbers. It is based on the principle that the GCD of two numbers is equal to the GCD of the smaller number and the remainder of the larger number divided by the smaller number.

2. Why is the Euclidian Algorithm important?

The Euclidian Algorithm is important because it is the most efficient method for finding the GCD of two numbers. It is also used in various other mathematical calculations, such as finding the least common multiple and solving linear Diophantine equations.

3. How is the Euclidian Algorithm proved?

The Euclidian Algorithm can be proved using the principle of mathematical induction. The base case is when the smaller number is equal to 0, in which case the GCD is the larger number. For the inductive step, it is assumed that the algorithm works for two numbers, and then it is shown that it also works for the next set of numbers using the remainder and the smaller number.

4. Can the Euclidian Algorithm be used for more than two numbers?

Yes, the Euclidian Algorithm can be extended to find the GCD of multiple numbers. This is done by finding the GCD of the first two numbers, and then using that GCD and the third number to find the GCD of all three numbers, and so on until all numbers have been considered.

5. Can the Euclidian Algorithm be used for numbers other than integers?

Yes, the Euclidian Algorithm can be used for any type of numbers that can be divided and have a remainder. This includes rational numbers and even complex numbers. The same principle of finding the GCD of the smaller number and the remainder of the larger number divided by the smaller number applies in these cases as well.

Similar threads

Replies
13
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
878
  • Linear and Abstract Algebra
Replies
17
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
267
Replies
2
Views
1K
  • General Math
Replies
5
Views
766
  • General Math
Replies
1
Views
2K
Replies
2
Views
1K
  • General Math
Replies
2
Views
849
  • Introductory Physics Homework Help
Replies
27
Views
2K
Back
Top