A Theorem to Find Lattice Points

Date: 6/1/96 at 21:37:16
From: Anonymous
Subject: A Theorem to Find Lattice Points

I need to know the theorem which gives the conditions under which the 
line ax+by=c will contain lattice points.

I have not been able to find it anywhere.

Date: 6/1/96 at 23:7:0
From: Doctor Pete
Subject: Re: A Theorem to Find Lattice Points

This is more of a number theory question than a geometry question. If 
a and b are relatively prime integers, then there exist an infinite 
number of integer solutions (x,y) such that ax+by=1, so (cx,cy) will 
be lattice points on the line ax+by=c. To see if there are an infinite 
number of solutions, we apply the Euclidean Algorithm. Here's an 
example:

  a=13, b=37, so we wish to solve 13x + 37y = 1 for integers x,y.

  37 = 2(13) + 11    [eq. 1]
  13 = 1(11) + 2     [eq. 2]
  11 = 5(2) + 1      [eq. 3]     <-- stop when remainder is 1.

Then

  1 = 1(11) - 5(2)                    [from eq. 3]
                2 = 1(13) - 1(11)     [from eq. 2]
  ---------------------------
  1 = 1(11) - 5(1(13) - 1(11)) = 6(11) - 5(13)
                                   11 = 1(37) - 2(13)  [from eq. 1]
                             ------------------
                         1 = 6(1(37) - 2(13)) - 5 (13)

so 1 = 6(37)-17(13); hence (x,y) = (-17,6). Note if (x,y) is a 
solution to ax+by=1, then (bkx,-aky) is a solution for all nonzero 
integers k.

So what if a and b are not relatively prime? Then they have a greatest 
common divisor d. If c does not share this common divisor, then it is
immediately obvious that no integer solution exists to ax+by=c, since 
the lefthand side will always have d as a factor. Hence d must divide 
c; if so, then we can divide the entire equation by d and we get some 
a'x+b'y=c', where a' and b' are relatively prime, which we have seen 
has a solution. So the condition for a solution is:

            gcd(a,b) | c

that is, the greatest common divisor of a and b must divide c. (This
includes the relatively prime case, since 1 divides c)

-Doctor Pete,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/