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 'Trigonometry problem of interest'

Seemingly by some mathematical coincidence, a hexagon of sides 2,2,7,7, 11, and 11 can be inscribed in a circle of radius 7. The other day I saw a math problem on line, which they said came from a Polish Olympiad, where you compute the length x of the 3rd side which is the same as the radius, so that the sides of length 2,x, and 11 are inscribed on the arc of a semi-circle. The law of cosines applied twice gives the answer for x of exactly 7, but the arithmetic is so complex that the...
View full post »

Similar threads

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