Associated Topics || Dr. Math Home || Search Dr. Math

### 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/
```
Associated Topics:
High School Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search