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
AI Thread 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 'What Exactly is Dirac’s Delta Function? - Insight'

Insights auto threads is broken atm, so I'm manually creating these for new Insight articles. In Dirac’s Principles of Quantum Mechanics published in 1930 he introduced a “convenient notation” he referred to as a “delta function” which he treated as a continuum analog to the discrete Kronecker delta. The Kronecker delta is simply the indexed components of the identity operator in matrix algebra Source: https://www.physicsforums.com/insights/what-exactly-is-diracs-delta-function/ by...
View full post »

Thread 'Non-orthogonal bases'

Suppose ,instead of the usual x,y coordinate system with an I basis vector along the x -axis and a corresponding j basis vector along the y-axis we instead have a different pair of basis vectors ,call them e and f along their respective axes. I have seen that this is an important subject in maths My question is what physical applications does such a model apply to? I am asking here because I have devoted quite a lot of time in the past to understanding convectors and the dual...
View full post »

Thread 'A fully new path to prove Riemann Hypothesis'

For original Zeta function, ζ(s)=1+1/2^s+1/3^s+1/4^s+... =1+e^(-sln2)+e^(-sln3)+e^(-sln4)+... , Re(s)>1 If we regards it as some function got from Laplace transformation, and let this real function be ζ(x), that means L[ζ(x)]=ζ(s), then: ζ(x)=L^-1[ζ(s)]=δ(x)+δ(x-ln2)+δ(x-ln3)+δ(x-ln4)+... , this represents a series of Dirac delta functions at the points of x=0, ln2, ln3, ln4, ... , It may be still difficult to understand what ζ(x) means, but once it is integrated, the truth is clear...
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
1K
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

Hot Threads

Recent Insights

Back
Top