Thread: 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!

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.

Thanks!