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
1640 views around the world
You can reuse this answer
Creative Commons License