Hacker News Reader

It's not necessary that the set of numbers be coprime: {2,4} fed into Euclid's algorithm would proceed to reduce to {2,2} then {2,0} then yield {2}.

In general Euclid's algorithm is a special case of Buchberger's algorithm, q.v., if interested.

View on HN

It is definitely not necessary. Because the gcd of 2 and 4 is 2, thus we have 2(1) and 2(2). 2 and 1 are coprime and thus will reduce down to 1, the common part left out is 2 and the uncommon part is 1, as always 1.

Thanks about the Buchberger intro I didn't know about that.

What's q.v?

Also, Buchberger is a special case of Knuth-Bendix completion :D

> What's q.v?

"quod vide" = "which see": https://en.wiktionary.org/wiki/quod_vide .

So basically "see also" in Latin?

good point: "see" even by itself works, but i had lots of Latin so didn't think of it.

yep...fun stuff.

https://www.amazon.com/Ideals-Varieties-Algorithms-Computati...

covers much of this topic

Reply on news.ycombinator.com