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

1 Answer
Monzur R.
Dec 5, 2017

#x=-140# and #y=257#

Explanation:

To find #x# and #y#, we must first find #gcd(648,353)# using Euclid's algorithm.

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

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

#295=5*58+5# so #gcd(295,58)=gcd(58,5)#

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

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

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

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

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

#648x+353y=1#

#=3-2#

#=58-11*5-(5-3)#

#=58-12*5+(58-11*5)#

#=2*58-23*5#

#=2(353-295)-23(295-5*58)#

#=2*353-25*295+115*58#

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

#=142*353-25*648-115*295#

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

#=142*353-25*648-115*(648-353)#

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

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

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