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
Join the discussion
Registration is free. Ask a follow-up in this thread, or start your own.
1 reply · 1K views
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.