2
$\begingroup$

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?

$\endgroup$
1
  • $\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$ Jan 20, 2018 at 11:43

1 Answer 1

2
$\begingroup$

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?

$\endgroup$
4
  • $\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$
    – user
    Jan 20, 2018 at 12:47
  • $\begingroup$ can you please elaborate on that. $\endgroup$ Jan 20, 2018 at 12:50
  • $\begingroup$ @bhavindhedhi for example $gdc(4,3)=1$ and $-2*4+3*3=1$ but also $4*4-5*3=1$ $\endgroup$
    – user
    Jan 20, 2018 at 12:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.