Is there an algorithm for finding x and y in a GCD problem?

[Poirot1]

Since 2 is gcd of 2008 and 8002, I can write 2=2008x+8002y for integers x and y. Is there an algorithm for finding x and y?

 

[CaptainBlack]

Since 2 is gcd of 2008 and 8002, I can write 2=2008x+8002y for integers x and y. Is there an algorithm for finding x and y?

Euclid's Algorithm and Bezout's identity or the Extended Euclidean Algorithm

CB

 

[Poirot1]

meaningless computer jargon I'm afraid. Can you apply the method to the example given please?

 

[CaptainBlack]

meaningless computer jargon I'm afraid. Can you apply the method to the example given please?

\( 8002 = 3 \times 2008 + 1978 \)

\( 2008 = 1 \times 1978 + 30 \)

\(1978 = 65 \times 30 + 28\)

\(30 = 1 \times 28 + 2\)

so:

\[ \begin{array}{ ccccc } 2 &=& 30& -& 28 \\ &=& 30 &-& (1978-65 \times 30 ) \\ &=& 66 \times 30 & - & 1978 \\ &=& 66 \times(2008-1978)&-&1978 \\ &=& 66 \times 2008& -& 67 \times 1978 \\ &=& 66 \times 2008&-& 67 \times (8002-3 \times 2008) \\ &=&(-67)\times 8002&+&267\times 2008 \end{array}\]

CB

 

[Poirot1]

You should modify wikipedia article.