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

  • Thread starter Thread starter Poirot1
  • Start date Start date
  • Tags Tags
    Gcd
Click For Summary
The discussion centers on finding integers x and y in the equation 2 = 2008x + 8002y, where 2 is the GCD of 2008 and 8002. The Extended Euclidean Algorithm is suggested as a method to solve this problem. A step-by-step application of the algorithm is provided, demonstrating how to derive the coefficients for x and y. The final result shows that x = 267 and y = -67. The conversation highlights the practical application of theoretical concepts in number theory.
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.
 

Thread 'Area of Overlapping Squares'

Here is a little puzzle from the book 100 Geometric Games by Pierre Berloquin. The side of a small square is one meter long and the side of a larger square one and a half meters long. One vertex of the large square is at the center of the small square. The side of the large square cuts two sides of the small square into one- third parts and two-thirds parts. What is the area where the squares overlap?
View full post »

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