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

  • Context: MHB 
  • Thread starter Thread starter Poirot1
  • Start date Start date
  • Tags Tags
    Gcd
Click For Summary
SUMMARY

The discussion centers on finding integers x and y in the equation 2 = 2008x + 8002y, where 2 is the greatest common divisor (GCD) of 2008 and 8002. The Extended Euclidean Algorithm is identified as the method to derive x and y. The participants demonstrate the algorithm through a series of calculations, ultimately expressing the solution as x = 267 and y = -67. This confirms the applicability of Bezout's identity in solving GCD problems.

PREREQUISITES
  • Understanding of the Extended Euclidean Algorithm
  • Familiarity with Bezout's identity
  • Basic knowledge of integer equations
  • Proficiency in performing polynomial long division
NEXT STEPS
  • Study the Extended Euclidean Algorithm in detail
  • Explore applications of Bezout's identity in number theory
  • Practice solving GCD problems using integer linear combinations
  • Learn about polynomial long division techniques
USEFUL FOR

Mathematicians, computer scientists, and students studying number theory or algorithms, particularly those interested in GCD calculations and integer solutions.

Poirot1
Messages
243
Reaction score
0
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?
 
Mathematics news on Phys.org
meaningless computer jargon I'm afraid. Can you apply the method to the example given please?
 
Poirot said:
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
 
You should modify wikipedia article.
 

Similar threads

MHB Why Choose Euclid's Algorithm Over Prime Decomposition for Calculating GCD?
  • · Replies 1 ·
Replies
1
Views
1K
MHB Is $\gcd(n, n+2) = 1$ or $2$ for any integer $n$?
  • · Replies 5 ·
Replies
5
Views
2K
MHB Finding the Greatest EVEN Factor of X: Solving the GCD of m,n=2
  • · Replies 19 ·
Replies
19
Views
5K
Undergrad ##x\lt y \lt z## positive integer numbers and if ##\dfrac 1x+\dfrac 1y+\dfrac 1z=\dfrac 13##
  • · Replies 6 ·
Replies
6
Views
2K
Use the Euclidean algorithm to find integers ## a, b, c ##
  • · Replies 5 ·
Replies
5
Views
1K
Working Backwards from the GCD: Finding the Solution to a GCD Calculation
  • · Replies 5 ·
Replies
5
Views
2K
Find lcm(143, 227), lcm(306, 657), etc.? Can anyone verify my work?
  • · Replies 7 ·
Replies
7
Views
3K
Proving an integer is composite
  • · Replies 13 ·
Replies
13
Views
1K
MHB How Do You Prove That sa + tb Divides gcd(a, b) in Bezout's Lemma?
  • · Replies 3 ·
Replies
3
Views
3K
Undergrad Questions regarding Kurepa's Conjecture
  • · Replies 1 ·
Replies
1
Views
2K