GCD and the magic of subtraction

Re:GCD and the magic of subtraction by plumsempy on Tuesday August 25, 2020 @08:04PM (#24277697)

yeah~ its clicking a bit more now, thank you. I am comfortable with the fact that the remainder is a coprime of a and b; but that corprimes have a definitive path to 1 is strange. Why now 0 or -1? or -2? it is not clear to me why it must always converge to 1.

[ Parent | on HN ]

Re:GCD and the magic of subtraction by phaemon on Sunday August 30, 2020 @10:57AM (#24323320)

Well, it can't hit zero because you'd need equal numbers for that, and they're not coprime ;)

It can't be negative because you cheat and always put "larger - smaller". See your own example: you go:

    13 - 7 = 6 -> 7 - 6 = 1
     a - b = c -> b - c = d

But then then you do:

    6 - 1 = 5 -> 5 - 1 = 4
    a - b = c -> c - b = d

Which switches the order. What if you don't?

[ Parent | on HN ]