I know you can write gcd of two numbers as a linear combination of two numbers, but my question is what do we achieve by doing that? is there any significance of writing gcd as linear combination? does that give us some more interesting info about gcd and those two numbers?
-
$\begingroup$ In many arithmetic algorithms, it's handy to be able to invert a number $a$ modulo another number $n$, that is to solve $ax\equiv1\pmod n$. $\endgroup$– Angina SengJan 20, 2018 at 11:43
1 Answer
That result is known as Bézout's identity and it is very useful to solve many problems in number theory as for example the calculation of the modular inverse.
Take also a look here What is the importance of Bézout's identity?
-
$\begingroup$ Thanks for the answer but does this linear combination has something to do with space transformation like 1d integer space to some other space, where a point from 1d represents some fine area in that transformed space? $\endgroup$ Jan 20, 2018 at 12:45
-
$\begingroup$ @bhavindhedhi it is another kind of linear combination here, indeed, for example, it is not unique. $\endgroup$– userJan 20, 2018 at 12:47
-
-
$\begingroup$ @bhavindhedhi for example $gdc(4,3)=1$ and $-2*4+3*3=1$ but also $4*4-5*3=1$ $\endgroup$– userJan 20, 2018 at 12:52