Numbers, A Lattice of Integer Solutions

A Lattice of Integer Solutions

For fixed nonzero integers s and t, find all integers x and y such that xs + yt = 0. This is an example of a diophantine equation, (biography), where the variables must be integers, or in some cases, rational numbers. In this case there is no need to ask about rational numbers, since we can always multiply through by the common denominator and get integers back again.

For clarity, write xs = -yt. Clearly x and y are restricted to a line in the plane, passing through the origin, with slope -s/t. If g is the gcd of s and t, divide through by g. Since s/g and t/g are now relatively prime, s/g always divides y and t/g always divides x. In fact x ÷ t/g = -y ÷ s/g. Call this common quotient k. Conversely, for any integer k, we can construct a pair x y that satisfies the equation.

The solutions form a regularly spaced series of dots along the slanted line in the plane, one dot for each value of k. The origin corresponds to k = 0. The line contains all solutions in real numbers; the periodic points on the line are the solutions with integer x and y coordinates. This is a one dimensional lattice.

Solutions of 4x+6y=0

Find all x and y satisfying xs + yt = n.

If n is 0 we are done, as shown above. If g, the gcd of s and t, does not divide n, there are no solutions. If n = g×c, use Euclid's algorithm to find a solution for xs + yt = g, then multiply x and y by c.

If there are two different solutions to xs + yt = n, subtract them to find a point on the lattice described above. Conversely, any point on this lattice can always be added to a base solution to get another solution to xs + yt = n. The solutions are precisely a shifted version of the aforementioned lattice. The line of points doesn't pass through the origin any more; it is shifted so that the sum xs+yt is always n, rather than 0.

Solutions of 4x+6y=4

Find integers x, y, and z satisfying xs + yt + zu = 0.

When z = 0, solve xs + yt = 0, as we did before. this gives a series of colinear points in the z=0 plane, passing through the origin. If g, the gcd of s and t, does not divide u, z is forced to take up the slack. Let v be that portion of g that is not covered by u, and set z = v. Now solve xs + yt = -uv, as we did above. This gives a shifted version of the line of points. In other words, as we move up one level, to z = v, the line of points shifts by just the right amount to produce -uv. Advance to z = 2v, and the base solution is doubled. In other words, the line of points is shifted by twice as much, to produce -2uv. This continues forever, for all levels z = kv. The integer solutions form a two dimensional lattice within a tilted plane that cuts through the origin. If we concentrate on the plane itself, the lattice defines a repeating pattern of parallelograms. Each parallelogram is a copy of the base cell.

If the equation is xs + ty + zu = n, use Euclid's algorithm with backtracking to find a particular solution, then shift the previous planar lattice by that much. Now the plane of parallelograms, a two dimensional lattice, has been pushed away from the origin.

As you have probably surmised, this procedure continues through any number of variables. The integer solutions to wr + xs + yt + zu = n form a three dimensional lattice in four space, shifted away from the origin. Needless to say, this is difficult to picture in higher dimensions, but it is perfectly valid, algebraically.

Solutions of 4x+2y+5z=23