- #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

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- 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

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 ?

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.

- #10

- 1,356

- 2

you find it by the extended algorithm

Share: