A Theorem to Find Lattice PointsDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/