THE GENERAL SOLUTION OF THE INDETERMINATE
EQUATION: Ax + By + Cz +

BY D. N. LEHMER

= 1.

DEPARTMENT OF MATHEMATICS, UNIVERSITY OF CALIFORNIA

Communicated by E. H. Moore, January 30, 1919

Little has been done since Jacobi (Werke, 6, 355) in connection with the solution of the general linear indeterminate equation. Jacobi has given no less than four methods all involving the reduction of the equation by means of a set of auxiliary equations to the solution of an equation in two variables the solution of which is immediately obtained from the theory of the ordinary continued fraction. The solution here presented treats the general equation in the same non-tentative way that is found in the continued fraction solution for two variables. The method applies equally well when the right hand mem- 、 ber is zero and gives a perfectly general solution from which all other special solutions may be obtained.

Consider the set of positive or negative, non-zero integers a1, b1, C1,..., kı, li and let m be the number of terms in the set. We derive from this first set a second set a2, b2, C2, k2, l2 by means of the equations:

where if a is different from unity the numbers a1, B1, .

that a2, b2, C2,

bers b1, C1, unity then a1,

k2 are the smallest positive residues, not zero, of the num

kı, li respectively with respect to the modulus a1. If a1 is βι. K1 are taken equal to b1, c1, l respectively, so that in this case the second set consists of zeros with the exception of the last term, which is unity.

We derive in the same way a third set from the second by means of the equations:

As in the preceding set, if a2 is different from unity, we take the numbers α2, B2, . K2 so that aз, b3, kз are the smallest positive, non-zero residues

l2 respectively, modulo az. If a2 is unity, a2, B2, .

.

K2 are taken

equal respectively to b2, C2, · l2, and in this case the third set consists of zeros with the exception of the last, ls, which is unity.

an + 1

Continuing this process, if the original set had no common factor other than unity, we must arrive at a set in which the first number is unity. For it is clear that an +1 < an except when b, is divisible by an in which case = an. Further an + 2 < an except when both b and c are divisible by an, in which case an + 2 = An+1 = An, and so on. If now the original set had the greatest common divisor unity so will also the set an, bn, cn, · kn, ln, and so not all the numbers bn, Cn, . . . kn, In can be divisible by an. After a number of steps in the process at most equal to n 1 an ax must appear which is less than an and not zero. In the same way another set must appear in which the first number is less than ax and so on. This process must then lead to a set in which the first number is unity. By taking one more step a set is then obtained in which the numbers are all zeros except the last which is unity.

...

We proceed now to reverse the above process, and taking the numbers α1, B1, . . . K1: α2, B2, . . . K2: . . as given we will show how to reconstruct the original set a1, bi, c1, k1, l1 from them. We construct first a determinant of order m in which the element of the prinicipal diagonal are all units, and all the other elements are zero. Using the first set of numbers α1, B1, . K1, which we will call the first 'partial quotient set' we construct what we will call the 'first determinant' as follows: The top row of the above determinant is erased and another row is added at the bottom which has for

its elements 1, α1, B1, . K1. This bottom row we will call the first 'convergent set' and for uniformity of notation we write it A1, B1, C1, . . . K1, L1. It is seen that the value of the first determinant is unity.

Using the second partial quotient set, a2, B2, . . . K2. we obtain from the first determinant a second determinant by erasing the top row and adding for the bottom row the second convergent set A2, B2, C2, . . . K2, L2, the elements of which are obtained by adding the columns of the first determinant after multiplying the first row by 1, the second by a2, the third by ẞ2, etc. and the bottom row by K2. In the same way we get the third determinant and the third convergent set, using the third partial quotient set as, B3,... Kз. The nth convergent set, which is the bottom row of the nth determinant is related to the preceding sets by the recursion formulae:

with similar formulae for the Bn, Cn, etc. It is clear from the way the determinants are derived from each other and from the original determinant that the value of each is unity.

We state now the remarkable theorem that the last convergent set is identical with the original set a1, b1, C1 . . . k1, li, from which the successive partial quotient sets were derived. This theorem comes out of the general theory of continued fractions, of multiplicity m, but without any appeal to that theory Professor Frank Irwin has derived it very simply from the following equations which are easily established by complete induction:

Now, as we have seen, in the last set an, bn, cn, kn are all zero, and ln is equal to unity. This gives the theorem.

This theorem throws into our hands a straightforward method of writing down a determinant equal to unity whose bottom row is any given set of positive or negative non-zero integers, with greatest common divisor unity. Let this last row be An, Bn, Cn,... Kn, Ln, and let the co-factors of these elements in the last determinant be A, B, C'n, . . . K'n, L'n. Then these co-factors furnish a set of values for the unknown in the indeterminate equation Anx + By +... Lv 1, and by multiplying these values through by r we get a solution of the equation when the right member is equal to r. Moreover since AnA'. + B„B' + С„C2 + . . . K„K'% + L„L'2 = 0 for m + 1 we may write for the most general value

1, n p = n of the variables:

2.

n

=

x=rAn+sAn-1 + tAn-2 +...

y=rBsB-1+tB-2 +

z = rCn + sCn−1 + tCn-2 +

+pAn-m+1+qAn-m
pBn-n
Sn-m+1 + qB'1.
+pCn-m+1+qCn-m

n-m

That this is the most general form of the solution follows from the fact since the determinant of the co-factors is unity a set of integer values of r, s, t, Þ, q can always be found for any given set of values of x, y, z,

We give as a numerical example the problem of determining the most general solution of the indeterminate equation:

33x+55y+79z — 99w = r.

The following is a convenient arrangement of the work of computing the sets ai, bi, ci, di, α1, B1, Y1, etc.

With these values of an, ẞn, Yn we proceed to compute the successive convergent sets and the corresponding determinants. The following is a convenient arrangement of the work:

The last determinant yields us the solution of the proposed problem. Computing the minors we easily get the following general values for the unknowns in the equation:

Communicated by Henry F. Osborn, February 6, 1919

Introductory. Since my last communication to the PROCEEDINGS OF THE NATIONAL ACADEMY (Vol. 3, pp. 192-195) two years ago, concerning the time distribution of aboriginal traits in the Mammoth Cave region of Kentucky, it has become possible to report upon the stratigraphic conditions in two additional North American culture centers. One of these new centers, viz., the Florida-Georgia characterization area, directly adjoins that in which the Mammoth Cave occurs, in fact is in a large sense one with it and need not therefore be specifically discussed. The other center, of special concern here is sepa

rated from the preceding by the totally different Plains culture area and lies in the semi-arid plateau region known culturally as the Pueblo area and geographically as the Southwest. The mentioning of these three distinct and partly separated centers together in this place is made possible and necessary by the fact that our archaeological findings in them are identical in their general import, as will be brought out at the end of the discussion.

The Pueblo culture area is from several standpoints our most profitable field for the study of primitive man. It is to us what Egypt is to the Old World and more. For not only have we here an abundance of ruins more or less ancient but we have the relatively unspoiled descendants of the builders still surviving, and we have documentary data concerning them reaching back nearly four hundred years. It is a field therefore in which the ethnologist, the historian, and the archaeologist can work hand in hand; and, needless to say, they have done so. Each mode of approach has, however, its particular limitations; and it has of late become evident that an adequate solution of the problem presented lies in a coordination of effort. The ethnologist, e.g., sees the problem clearly only in its spatial dimension; the historian makes a brief beginning with the time projection but to complete his work he must of necessity appeal to the archaeologist. The archaeologist, on the other hand, while he may see the problem in both dimensions, unless already an ethnologist, is obliged to call upon such a specialist to assist him in the interpretation of his findings. The failure to fully appreciate these interrelations will probably in a large measure explain the history of anthropological investigation in the Southwest.

History of Archaeological Investigation.-The Pueblo culture area has been under consideration for seventy-three years and something like three stages are discernible in the process. Of the numerous reports now available on the antiquities, those of the first thirty years were written by staff members of various governmental expeditions and surveys and were of a general descriptive character. About 1880 the investigation became institutionalized, so to speak. Specialists in history, ethnology, and archaeology entered the field. and all have delivered more or less convincing reports on the problem from their particular points of view. But, naturally enough, only the historian has in any sense finished his task. The ethnologist has his work well under way; while as for the archaeologist-in spite of all he has done and written-his results have not until lately been carried much beyond the analytic stage. During the last few years finally there has been a distinct effort on the part of several investigators to reach the synthetic level or in other words to get beyond the descriptive and classificatory routine work to really interpretative results. It is pleasant in this connection to be able to say that the American Museum's archaeological work, prolonged now for seven years and taken part in by Messrs. Leslie Spier and Earl H. Morris as well as the writer, has been primarily of this interpretative character. We have entered the field not so much to recover specimens as to solve problems. Owing to the immensity of the