Can the Extended Euclidean Algorithm Solve Equations in Number Theory?

[Bob19]

Hi I got a question:

I have the following problem ax + by = c. Where a,b are positive integers, and c is a known integer.

If I calculate the gcd(a,b) is it then possible to find the x,y which makes the above equation true ?

Best Regards,
Bob

 

[neurocomp2003]

yes...there are many solutions if gcd|c. no solution if it doesn't

its known (I hope in the right order):
"The linear Congruence THeorem" (go check mathworld.com)
What you do is use the extended GCD(euclid) algorithm.

 

[Bob19]

Please bear with me,

ax + by = c. Then if gcd(a,b) is different from 'c' then there doesn't exist any x,y which makes the equation true?

And this is derived from The extended euclidian algorithm ?

/Bob

yes...there are many solutions if gcd|c. no solution if it doesn't

its known (I hope in the right order):
"The linear Congruence THeorem" (go check mathworld.com)
What you do is use the extended GCD(euclid) algorithm.

 

[neurocomp2003]

no the derivation i think comes from another proof. You use the extended euclidian
to find x0,y0. With that pairing you can find all solutions if they exist(distinct congruences)

and its not gcd=c its gcd|c...guess you haven't seen this notation before..it means gcd divides c (or maybe i have it bkwds, c|gcd) either way it means gcd is a factor of c.
go to mathworld.com..its a nice source of math stuff.

 

[Bob19]

Thank You :-)

/Bob

no the derivation i think comes from another proof. You use the extended euclidian
to find x0,y0. With that pairing you can find all solutions if they exist(distinct congruences)

and its not gcd=c its gcd|c...guess you haven't seen this notation before..it means gcd divides c (or maybe i have it bkwds, c|gcd) either way it means gcd is a factor of c.
go to mathworld.com..its a nice source of math stuff.

 

[Bob19]

On last question,

This is how I understand the gcd-part of the euclidian algorithm.

If gcd(a,b) is larger than 1, then there is no solution for ax+by = c ?

/Bob

Thank You :-)

/Bob

 

[neurocomp2003]

no heh best ot use an example. k

First the theory
linear congruence theorem states
ax+by=gcd(a,b) always has many(finite number) solutions of which you can find a pair(X0,Y0) FROM
GCDext.

however your equation is ax+by=c. Hopefully you'll see what sgoing on...
inorder for this 2nd eq'n to have a solution c must be a multiple of g.
thus ax+by=c=kg. since you can find solutions ax+by=g...you can find solutions for ax+by=kg. Do you see how?

Now the example.
so 4x+6y=2...(-1,1) is a sol'n
and 4x+6y=8...(-4,4) is a sol'n where k=4
and 4x+6y=7..(no sol'n)...2 does not divide 7.

since g = 2--> 2(2x)+2(3y)=7 ...2 does not divide into 7. no solution can be found.

 

[Bob19]

Thank You again for Your answer,

I have used the day to study the extend euclidian algorithm.

and I have a question.

Once again we have the equation ax + by = c and d = gcd(a,b)

If 'd' does divide into 'c', 'a', 'b' how do I find 'x' and 'y' ??

e.g. 510x+2850y = 60, Here gcd(a,b) = 30. Is there a specific method I can use to calculate x,y? Or is the only method doing the number in my head ?

Sincerely and Best regrads,

Bob

no heh best ot use an example. k

First the theory
linear congruence theorem states
ax+by=gcd(a,b) always has many(finite number) solutions of which you can find a pair(X0,Y0) FROM
GCDext.

however your equation is ax+by=c. Hopefully you'll see what sgoing on...
inorder for this 2nd eq'n to have a solution c must be a multiple of g.
thus ax+by=c=kg. since you can find solutions ax+by=g...you can find solutions for ax+by=kg. Do you see how?

Now the example.
so 4x+6y=2...(-1,1) is a sol'n
and 4x+6y=8...(-4,4) is a sol'n where k=4
and 4x+6y=7..(no sol'n)...2 does not divide 7.

since g = 2--> 2(2x)+2(3y)=7 ...2 does not divide into 7. no solution can be found.

 

[shmoe]

Once again we have the equation ax + by = c and d = gcd(a,b)

If 'd' does divide into 'c', 'a', 'b' how do I find 'x' and 'y' ??

e.g. 510x+2850y = 60, Here gcd(a,b) = 30. Is there a specific method I can use to calculate x,y? Or is the only method doing the number in my head ?

First find x, y, where ax+by=gcd(a,b). You know how to use the Euclidean algorithm to find gcd(a,b), you can work backwards from this to write the gcd as a linear combination of a and b. e.g. a=33, b=9.

33=3*9+6 (eq1)
9=1*6+3 (eq2)
6=2*3+0

so gcd(33,9)=3. (eq2) tells us 3=9-1*6. (eq1) tells us 6=33-3*9, substitute this into (eq2) to get:

3=9-1*(33-3*9)=9-1*33+3*9=9*(4)+33*(-1)

and we have x=4, y=-1.

So if we wanted x, y with 9x+33y=6 say, we'd multiply by 2 and take x=4*2=8, y=(-1)*2=-2.

 

[neurocomp2003]

you find it by the extended algorithm