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 'Erroneously finding discrepancy in transpose rule'

Thread 'Erroneously finding discrepancy in transpose rule'

Obviously, there is something elementary I am missing here. To form the transpose of a matrix, one exchanges rows and columns, so the transpose of a scalar, considered as (or isomorphic to) a one-entry matrix, should stay the same, including if the scalar is a complex number. On the other hand, in the isomorphism between the complex plane and the real plane, a complex number a+bi corresponds to a matrix in the real plane; taking the transpose we get which then corresponds to a-bi...
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
I ##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
I Questions regarding Kurepa's Conjecture
  • · Replies 1 ·
Replies
1
Views
2K