Integer solutions to linear equation?

[Michael Hudson]

grant at nowhere. (Grant Edwards) writes:

> 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....

I hope I count ...

> 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.

Use Euclid's algorithm; here's some code that does that:

def find_hcf_as_lc(x0,y0):
    """ return h,q,r st h==q*x0+r*y0 """
    x=abs(x0); y=abs(y0)
    qn1=rn=1
    rn1=qn=0
    while y:
        (q,y),x=divmod(x,y),y
        qn,qn1=qn1-q*qn,qn
        rn,rn1=rn1-q*rn,rn
    if x0<0: qn1=-qn1
    if y0<0: rn1=-rn1
    return x,qn1,rn1

def solve(m,n,a):
    """ solve(m,n,a:Integer) -> (Integer,Integer)

find integers (x,y,r,s) such that (m+u*r)*x+(n+u*s)*y==a 
for all integers u."""
    h,x,y = find_hcf_as_lc(m,n)
    if a%h <> 0:
        raise "no solution"
    else:
        return (x*a/h,y*a/h,n/h,-m/h)

Then:

>>> solve(64,-41,1)
(-16, -25, -41, -64)

And your solution is:

(-16 - -41)*64 + (-25 - -64)*-41

I feel I must have neater code knocking about somewhere to do this,
but I can't find it right now.

Cheers,
M.

-- 
  it's not that perl programmers are idiots, it's that the language
  rewards idiotic behavior in a  way that no other language or tool 
  has ever done                        -- Erik Naggum, comp.lang.lisp