How do I solve 648x+353y=1648x+353y=1 for xx and yy working backwards from Euclid's algorithm for gcd(648,353)gcd(648,353)?

1 Answer
Monzur R.
Dec 5, 2017

x=-140x=−140 and y=257y=257

Explanation:

To find xx and yy, we must first find gcd(648,353)gcd(648,353) using Euclid's algorithm.

648=353+395648=353+395 so gcd(648,353)=gcd(353,295)gcd(648,353)=gcd(353,295)

353=295+58353=295+58 so gcd(353,295)=gcd(295,58)gcd(353,295)=gcd(295,58)

295=5*58+5295=5⋅58+5 so gcd(295,58)=gcd(58,5)gcd(295,58)=gcd(58,5)

58=11*5+358=11⋅5+3 so gcd(58,5)=gcd(5,3)gcd(58,5)=gcd(5,3)

5=3+25=3+2 so gcd(5,3)=gcd(3,2)gcd(5,3)=gcd(3,2)

3=2+13=2+1 so gcd(3,2)=gcd(2,1)gcd(3,2)=gcd(2,1)

2=1*2+02=1⋅2+0 so gcd(2,1)=gcd(1,0)=gcd(648,353)=1gcd(2,1)=gcd(1,0)=gcd(648,353)=1

Now we have 648x+353y=1648x+353y=1. But using the steps above, we can substitute in values until we get the equation in terms of multiples of 648648 and 353353.

648x+353y=1648x+353y=1

=3-2=3−2

=58-11*5-(5-3)=58−11⋅5−(5−3)

=58-12*5+(58-11*5)=58−12⋅5+(58−11⋅5)

=2*58-23*5=2⋅58−23⋅5

=2(353-295)-23(295-5*58)=2(353−295)−23(295−5⋅58)

=2*353-25*295+115*58=2⋅353−25⋅295+115⋅58

=2*353-25(648-353)+115(353-295)=2⋅353−25(648−353)+115(353−295)

=142*353-25*648-115*295=142⋅353−25⋅648−115⋅295

=2*353-25(648-353)+115(353-295)=2⋅353−25(648−353)+115(353−295)

=142*353-25*648-115*(648-353)=142⋅353−25⋅648−115⋅(648−353)

=-140(648)+257(353)=−140(648)+257(353)

so x=-140x=−140 and y=257y=257

Related questions
Impact of this question
1635 views around the world
You can reuse this answer
Creative Commons License