4 ms·
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
by jjtheblunt 6y ago
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.
- bollu 6y agoWhat's q.v? Also, Buchberger is a special case of Knuth-Bendix completion :D
- JadeNB 6y ago> What's q.v? "quod vide" = "which see": https://en.wiktionary.org/wiki/quod_vide https://en.wiktionary.org/wiki/quod_vide .
- m12k 6y agoSo basically "see also" in Latin?
- jjtheblunt 6y agogood point: "see" even by itself works, but i had lots of Latin so didn't think of it.
- jjtheblunt 6y agoyep...fun stuff. https://www.amazon.com/Ideals-Varieties-Algorithms-Computational-Undergraduate/dp/3319167200/ https://www.amazon.com/Ideals-Varieties-Algorithms-Computati... covers much of this topic
- plumsempy 6y agoIt 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.