- #1

- 71

- 0

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

- Thread starter Bob19
- Start date

- #1

- 71

- 0

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

- #2

- 1,356

- 2

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.

- #3

- 71

- 0

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

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

neurocomp2003 said:

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.

Last edited:

- #4

- 1,356

- 2

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.

- #5

- 71

- 0

/Bob

neurocomp2003 said:

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.

- #6

- 71

- 0

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

Bob19 said:Thank You :-)

/Bob

- #7

- 1,356

- 2

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.

- #8

- 71

- 0

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

neurocomp2003 said:

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.

- #9

shmoe

Science Advisor

Homework Helper

- 1,992

- 1

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.Bob19 said: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 ?

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.

- #10

- 1,356

- 2

you find it by the extended algorithm