Integer solutions to linear equation?

[Bruce Wolk]

ax + by = c, where a, b, and c are integers, and the solution (x,y) must
be an integer, is one of the simplest Diophantine equations.  There is
an algorithm, but at the moment I can't remember it.  I do recall that
if the greatest common divisor of a and b divides c, then there are
infinitely many solutions, otherwise there are none.  Thus, if c = 1,
there are always infintely many solutions if a and b are relatively
prime, as in your example.

You probably can find the algorithm in any basic book on number theory.

Bruce



Grant Edwards wrote:
> 
> This isn't really a Python question, but my example is in
> Python, and there seem to be plenty of people who know a fair
> bit of math here....
> 
> A friend of mine ran across a brain-teaser involving a bunch of
> flowers, some magic bowls and some other camoflage text.  What
> you end up with is having to solve the equation
> 
>      64x = 41y + 1
> 
> Where x and y are both integers.  After scratching our heads
> for a while, we used the brute force approach:
> 
> for x in range(1,100):
>     y = ((64*x)-1)/41
>     if 64*x == 41*y+1:
>         print (x,y)
> 
> The results:
> 
>   (25, 39)
>   (66, 103)
> 
> 25 was the expected solution, so we got both the equation and
> the Python snippet correct.  Is there a non-iterative way to
> solve a linear equation when the results are contrained to be
> integers?  I don't remember anything from any of my math
> classes that seems relevent, but I didn't take any anything
> beyond what is required for all undergrad engineers.
> 
> --
> Grant Edwards                   grante             Yow!  I didn't order
>                                   at               any WOO-WOO... Maybe a
>                                visi.com            YUBBA... But no WOO-WOO!