# Finding Integer Solutions

• Feb 29th 2012, 07:24 AM
joatmon
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!
• Feb 29th 2012, 09:35 AM
emakarov
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.
• Feb 29th 2012, 04:13 PM
joatmon
Re: Finding Integer Solutions
Thanks!