Results 1 to 3 of 3

Math Help - Finding Integer Solutions

  1. #1
    Member
    Joined
    Jan 2011
    Posts
    156

    Finding Integer Solutions

    I have an equation in the form ax + by = 1 where a and b are known integers. I need to come up with a method to find the possible solutions for x and y, but the trick is that x and y must also be integers. So the usual algebraic linear graph doesn't work very well.

    Can anybody suggest a method to do this? Is there an algebraic way? I'm also open to using a TI-89 or Wolfram Alpha, if you know how to program these devices to accomplish this.

    Thank you!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,528
    Thanks
    773

    Re: Finding Integer Solutions

    This equation is solvable iff the greatest common divisor of a and b is 1, i.e., a and b are coprime. The numbers x and y can be found using the extended Euclidean algorithm (look at other sections of the article as well). The bottom of the article has a link to an applet that solves the equation. Another applet is found on cut-the-knot site. For an efficient way to solve the equation see this post.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jan 2011
    Posts
    156

    Re: Finding Integer Solutions

    Thanks!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. integer solutions
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 28th 2011, 09:07 AM
  2. Finding the integer solutions to an equation
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: February 12th 2011, 04:48 PM
  3. Replies: 2
    Last Post: May 8th 2010, 10:59 PM
  4. No integer solutions to x^4 + y^4=100
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 17th 2009, 10:04 AM
  5. Integer Solutions
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: July 31st 2009, 09:18 AM

Search Tags


/mathhelpforum @mathhelpforum