- Thread starter
- Banned
- #1

- Thread starter Poirot
- Start date

- Thread starter
- Banned
- #1

- Jan 26, 2012

- 890

Euclid's Algorithm and Bezout's identity or the Extended Euclidean AlgorithmSince 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?

CB

- Thread starter
- Banned
- #3

- Jan 26, 2012

- 890

\( 8002 = 3 \times 2008 + 1978 \)meaningless computer jargon I'm afraid. Can you apply the method to the example given please?

\( 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

- Thread starter
- Banned
- #5