# Math Help - Particular solution for diophantine equation

1. ## Particular solution for diophantine equation

54x+15y=6

I think that GCD(54,15)=3

But then i am lost.

2. ## Re: Particular solution for diophantine equation

Originally Posted by TriForce
54x+15y=6

I think that GCD(54,15)=3

But then i am lost.
well you can say

18x + 5y = 2

36x + 10y = 4

36x-4 = 10y

30x + 6x - 4 = 10y

(6x - 4) mod 10 = 0

x = 4

then 36*4 - 4 = -10y

140 = -10y

y = -14

checking 54(4) - 15(14) = 6

there are probably more systematic and formal ways of solving this

3. ## Re: Particular solution for diophantine equation

Ok, with a bit less flailing

54x+15y=6 ; simplify it by dividing any common factors, in this case 3

18x+5y=2 ; rewrite this to eliminate one variable via modulo arithmetic

5(3x+y) + (3x-2) = 0 ==> 3x-2 = 0 (mod 5) ; now solve this relatively simple modulo equation

3*4-2 = 10 = 0 (mod 5) so x=4

Now to solve for y simply plug in x above

18(4)+5y=2

5y=-70

y=-14

4. ## Re: Particular solution for diophantine equation

Hi,
You should know a systematic way to find a particular solution of ax + by = c. Such a Diophantine equation has a solution if and only if gcd(a,b) divides c. So in this case divide both sides by the gcd. to arrive at an equation of the form ax + by = c with gcd(a,b) = 1. Now use the extended Euclidean algorithm to find m and n with am + bn = 1. Then x=cm and y=cn satisfy the original equation.

Example:
54x + 15y = 6 yields 18x + 5y = 2.
By the Euclidean algorithm, 18(2) + 5(-7) = 1
So x=4 and y=-14 is a particular solution.