# GCD question

#### Poirot

##### Banned
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?

#### Poirot

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

#### CaptainBlack

##### Well-known member
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

#### Poirot

##### Banned
You should modify wikipedia article.