Numbers, A Lattice of Integer Solutions

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.

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.

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.