Integer solutions to linear equation?

Grant Edwards grant at nowhere.
Tue Apr 18 17:28:04 CEST 2000


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!



More information about the Python-list mailing list