Welcome to our community

Be a part of something great, join today!

GCD question

  • Thread starter
  • Banned
  • #1

Poirot

Banned
Feb 15, 2012
250
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

Well-known member
Jan 26, 2012
890
  • Thread starter
  • Banned
  • #3

Poirot

Banned
Feb 15, 2012
250
meaningless computer jargon I'm afraid. Can you apply the method to the example given please?
 

CaptainBlack

Well-known member
Jan 26, 2012
890
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
 
  • Thread starter
  • Banned
  • #5

Poirot

Banned
Feb 15, 2012
250
You should modify wikipedia article.