1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Number theory and gcb

  1. Sep 26, 2005 #1
    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,
  2. jcsd
  3. Sep 26, 2005 #2
    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.
  4. Sep 26, 2005 #3
    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 ?


    Last edited: Sep 26, 2005
  5. Sep 26, 2005 #4
    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.
  6. Sep 26, 2005 #5
    Thank You :-)


  7. Sep 26, 2005 #6
    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 ???


  8. Sep 26, 2005 #7
    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

    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. Sep 27, 2005 #8
    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,


  10. Sep 27, 2005 #9


    User Avatar
    Science Advisor
    Homework Helper

    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)

    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:


    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.
  11. Sep 27, 2005 #10
    you find it by the extended algorithm
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook