From: "Julio Gómez" <juliogg@arrakis.es>
Subject: RE: Integer solutions to systems of linear Equations
Date: Tue, 20 Jun 2000 08:38:25 +0200
Newsgroups: sci.math
Summary: [missing]

    Hi:

    This problem, as you state it, is known as Integer Linear Problem (ILP).

    It has been widely studied, and it is known to be in NP (Cook's theorem
[1971]). It's surprising you have found nothing about it in the net.

    Anyhow, it would help if you were a little more specific on the exact
problem you are dealing with, because there are special cases wich have nice
solutions, in despite of the general case.

    I strongly recommend you "Theory of Linear and Integer Programming" by
Alexander Schrijver [John Wiley & Sons 1986].

    Regards

        Julio


Hummel <hummel@kh-online.com> escribió en el mensaje de noticias
394EF20D.A35288A5@sfu.ca...
> Hi all,
>
> I'm doing a computational project in Number Theory, my topic is integer
> solutions to systems of linear equations.  Does anyone have any
> advice/links on this subject?  I just sorta picked it out of the blue,
> and haven't been able to find any good algorithms/information on the
> Net.  Any help would be appreciated.  Please e-mail me at jzliew@sfu.ca
>
> Thanks!
> Justin
>
==============================================================================

From: Fagan@dpt.com (Joe Fagan)
Subject: Integer solutions to systems of linear Equations
Date: 20 Jun 2000 08:20:51 -0400
Newsgroups: sci.math

Are you referring to systems of equations which look like
x=c1*m1 + r1, x=c2*m2 + r2,...,x=cn*mn + rn
If so, convert them to linear congruences
x=r1 (mod m1), x=r2 (mod m2),..., x=rn (mod mn)
Each equation may have a solution but there may be no simultaneous
solution (x=0 mod 2 and x=1 mod 4 will not have a simultaneous soln)
Then look up Chinese Remainder Theorem which tells you if a unique
(mod m1*m2*...*mn) soln exists. I think it says m1...mn must be
relatively prime in pairs. If you're using a computer then any chapter
on Applications of the Chinese Remainder Theorem will help you. By
hand however its much simpler to start with the equation with the
highest mod and work down solving the simpler linear congruences of
the form ax=r mod m as you go.

Joe Fagan