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

  • Context: Undergrad 
  • Thread starter Thread starter MienTommy
  • Start date Start date
  • Tags Tags
    Algorithm
Click For Summary
SUMMARY

The forum discussion centers on the Euclidean Algorithm, specifically addressing the transformation of the expression from +bc to -bc during the proof process. The user questions the derivation of d/(a-qb) instead of d/(a+qb), clarifying that the relationship d/a and d/bc leads to d/(a+bc). The discussion concludes that using a-qb simplifies calculations, as it reduces the size of the numbers involved, making it more efficient for subsequent steps in the algorithm.

PREREQUISITES
  • Understanding of the Euclidean Algorithm
  • Familiarity with algebraic manipulation of expressions
  • Knowledge of divisibility and common divisors
  • Basic concepts of number theory
NEXT STEPS
  • Study the properties of the Euclidean Algorithm in detail
  • Explore algebraic manipulation techniques for simplifying expressions
  • Learn about the implications of divisibility in number theory
  • Investigate the efficiency of different algorithms for finding greatest common divisors
USEFUL FOR

Mathematicians, students of number theory, educators teaching the Euclidean Algorithm, and anyone interested in algorithmic efficiency in mathematical proofs.

MienTommy
Messages
22
Reaction score
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
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.
 

Similar threads

Undergrad Five points in space with rational distances that are not co-linear
  • · Replies 13 ·
Replies
13
Views
3K
Does there exist a 2x2 non-singular matrix with only one 1d eigenspace?
  • · Replies 2 ·
Replies
2
Views
2K
High School "Neighbor fractions" in Gelfand's Algebra
  • · Replies 1 ·
Replies
1
Views
3K
Undergrad Non-Homogeneous Robin Boundary conditions and Interpretations of Signs
  • · Replies 2 ·
Replies
2
Views
3K
Undergrad Gradient descent algorithm and optimizers
  • · Replies 5 ·
Replies
5
Views
2K
Undergrad The Universe is No Simulation
  • · Replies 7 ·
Replies
7
Views
2K
Graduate Archimedes' area of a sphere proof; proposition 2
  • · Replies 2 ·
Replies
2
Views
2K
Undergrad Video on imaginary numbers and some queries
  • · Replies 3 ·
Replies
3
Views
2K
A and C collide with B inbetween; AB elastic, BC inelastic
  • · Replies 27 ·
Replies
27
Views
4K
Undergrad Is this proof of the least common multiple theorem in number theory valid?
  • · Replies 1 ·
Replies
1
Views
2K