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,
    Bob
     
  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 ?

    /Bob

     
    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 :-)

    /Bob

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

    /Bob

     
  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
    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. 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,

    Bob

     
  10. Sep 27, 2005 #9

    shmoe

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