Results 1 to 9 of 9

Math Help - Help finding an ax+by=c equation's integer solution

  1. #1
    Newbie panglot's Avatar
    Joined
    May 2011
    From
    Carbondale, IL
    Posts
    13

    Question Help finding an ax+by=c equation's integer solution

    Hello All,

    I have just begun a course on number theory and proofs, and I need help with the process of solving Diophantine equations. I am not sure how to employ the Euclidean algorithm to solve the following equation or how to go from that to the next step.

    2011x + 1492y = 10,000

    Could someone please explain the process to me? I need to determine whether this has integer solutions, but more importantly, I need to be able to understand and use this process on other such problems.

    Thank you very much for your time.

    Panglot
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1

    Re: Help finding an ax+by=c equation's integer solution

    Quote Originally Posted by panglot View Post
    Hello All,

    I have just begun a course on number theory and proofs, and I need help with the process of solving Diophantine equations. I am not sure how to employ the Euclidean algorithm to solve the following equation or how to go from that to the next step.

    2011x + 1492y = 10,000

    Could someone please explain the process to me? I need to determine whether this has integer solutions, but more importantly, I need to be able to understand and use this process on other such problems.

    Thank you very much for your time.

    Panglot

    Find gcg(1011,20)

    If c/(gcg(1011,20)) is integer the you have a solution(Theorem)


    Suppose that gcg(1011,20)=d, represent this d as linear combination(*) of 2011 and 20, now multiply d and (*) by k to get 1000, you will see one solution(x',y').

    How you can find parametric form of all solutions?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,412
    Thanks
    1328

    Re: Help finding an ax+by=c equation's integer solution

    Here is a look at a similar problem: 493x+ 215y= 100.

    215 divides into 493 two times with remainder 63: 63= 493- 2(215).

    63 divides into 215 three times with remainder 26: 26= 215- 3(63)

    26 divides into 63 twice with remainder 11: 11= 63- 2(26)

    11 divides into 26 twice with remainder 4: 4= 26- 2(11)

    4 divides into 11 twice with remainder 3: 3= 11- 2(4)

    3 divides into 4 once with remainder 1: 1= 4- 3

    Now we can replace that 3 by 11- 2(4) from the previous equation: 1= 4-(11- 2(4)= 3(4)- 11.

    We can replace that 4: 1= 3(26- 2(11))- 11= 3(26)- 7(11).

    And replace that 11: 1= 3(26)- 7(63- 2(26))= 5(26)- 7(63).

    And replace that 26: 1= 5(215- 3(63))- 7(63)= 5(215)- 22(63).

    And replace that 63: 1= 5(215)- 22(493- 2(215))= 49(215)- 11(493).

    Because we want 493x+ 215y= 100, not 1, multiply both sides of that previous equation by 100: (4900)(215)- (1100)(493)= 100.

    That tells us that one solution is x= -1100, y= 4900.

    But it is also easy to see that, for any integer k, x= -1100+ 215k, y= 4900- 493k is also a solution: 493(-1100+ 215k)+ 215(4900- 493k)= 493(-1100)+ (493)(215)k+ 215(4900)- (215)(493)k= 493(-1100)+ 215(4900) because the two "(215)(493)k" cancel.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie panglot's Avatar
    Joined
    May 2011
    From
    Carbondale, IL
    Posts
    13

    Re: Help finding an ax+by=c equation's integer solution

    HallsofIvy and Also Sprach Zarathustra, I have a question regarding extending this process:

    Say, for example, I use Euclid's Algorithm to calculate that two possible integer solutions to the equation 20y + 13x = 1000 are y=2000 and x=-2000. How might I be able to establish two inequalities that would indicate whether any other integers are possible solutions to this?

    Thank you both for your help--it is greatly appreciated.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1

    Re: Help finding an ax+by=c equation's integer solution

    Quote Originally Posted by panglot View Post
    HallsofIvy and Also Sprach Zarathustra, I have a question regarding extending this process:

    Say, for example, I use Euclid's Algorithm to calculate that two possible integer solutions to the equation 20y + 13x = 1000 are y=2000 and x=-2000. How might I be able to establish two inequalities that would indicate whether any other integers are possible solutions to this?

    Thank you both for your help--it is greatly appreciated.
    20*2000-13*1000 not equal to 1000.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie panglot's Avatar
    Joined
    May 2011
    From
    Carbondale, IL
    Posts
    13

    Re: Help finding an ax+by=c equation's integer solution

    I'm sorry, this should be 20*2000-13*3000=1000.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1

    Re: Help finding an ax+by=c equation's integer solution

    Quote Originally Posted by panglot View Post
    I'm sorry, this should be 20*2000-13*3000=1000.
    Here: Bézout's identity - Wikipedia, the free encyclopedia

    Under Algorithm...
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,412
    Thanks
    1328

    Re: Help finding an ax+by=c equation's integer solution

    If x_0 and y_0 satisfy ax+ by= c, then x= x_0+ bk, y= y_0- ak is also a solution for any integer k:

    a(x_0+ bk)+ b(y_0- ak)= ax_0+ abk+ by_0- abk= ax_0+ by_0= c
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie panglot's Avatar
    Joined
    May 2011
    From
    Carbondale, IL
    Posts
    13

    Re: Help finding an ax+by=c equation's integer solution

    HallsofIvy,

    Is there any way that one can set up some parameter of inequalities to establish whether or not x,y have solutions in the realm of natural numbers?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Finding the integer solutions to an equation
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: February 12th 2011, 04:48 PM
  2. Integer solution to power equation
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: December 11th 2010, 10:40 AM
  3. Finding the Solution in a Quadratic Equation?
    Posted in the Algebra Forum
    Replies: 1
    Last Post: February 27th 2010, 06:32 PM
  4. Replies: 7
    Last Post: September 2nd 2008, 04:01 PM
  5. wave equation - finding the solution
    Posted in the Calculus Forum
    Replies: 12
    Last Post: March 30th 2008, 03:09 AM

Search Tags


/mathhelpforum @mathhelpforum