Integer solutions to linear equation?

Grant Edwards grant at nowhere.
Tue Apr 18 18:52:18 CEST 2000


In article <38FC8CCF.B8B786CB at pacbell.net>, Bruce Wolk wrote:

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

I had a feeling that this required more number theory than I
know (an amount close enough to 0 that it can be safely
ignored).  :)

-- 
Grant Edwards                   grante             Yow!  I've got a COUSIN
                                  at               who works in the GARMENT
                               visi.com            DISTRICT...



More information about the Python-list mailing list