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

Discussion Overview

The discussion revolves around finding integers x and y in the equation 2 = 2008x + 8002y, where 2 is the greatest common divisor (GCD) of 2008 and 8002. The focus includes the application of algorithms such as the Extended Euclidean Algorithm in this context.

Discussion Character

  • Technical explanation, Mathematical reasoning, Debate/contested

Main Points Raised

  • One participant asks if there is an algorithm for finding integers x and y given the GCD of two numbers.
  • Another participant mentions the Extended Euclidean Algorithm and Bezout's identity as relevant methods for solving the problem.
  • Some participants express frustration with the technical jargon and request a direct application of the method to the specific example provided.
  • A detailed step-by-step application of the Extended Euclidean Algorithm is presented, showing how to express the GCD as a linear combination of the two numbers.
  • One participant suggests modifying a Wikipedia article, implying dissatisfaction with existing explanations or examples.

Areas of Agreement / Disagreement

Participants express differing levels of understanding and agreement on the clarity of the explanations provided. While some acknowledge the methods mentioned, others find them unclear and seek practical application.

Contextual Notes

Some participants indicate a lack of clarity in the initial explanations and request more concrete examples, highlighting potential limitations in the communication of the mathematical concepts involved.

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
3K
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
Undergrad Questions regarding Kurepa's Conjecture
  • · Replies 1 ·
Replies
1
Views
2K
MHB How can I prove that gcd(a,b) is an integer and gcd(a/b, b/h) = 1?
  • · Replies 2 ·
Replies
2
Views
2K