Reference / Paper · 1928
The Mechanical Combination of Linear Forms (Amer. Math. Monthly 35, 114–121)
D. H. Lehmer's own description of the 1926–28 bicycle-chain sieve, including its parallel spring-contact stopping circuit.
Reference / Paper · 1928
D. H. Lehmer's own description of the 1926–28 bicycle-chain sieve, including its parallel spring-contact stopping circuit.
The Mechanical Combination of Linear Forms D. H. Lehmer American Mathematical Monthly, Volume 35, Issue 3 (Mar., 1928), 114-121. Stable URL: http://links.jstor.org/sici?sici=0002-9890%28 192803 %2935%3A3%3C 114%3ATMCOLF%3E2.0.CO%3B2-Z Your use of the JSTOR archive indicates your acceptance of JSTOR’s Terms and Conditions of Use, available at http://www.jstor.org/about/terms.html. JSTOR’s Terms and Conditions of Use provides, in part, that unless you have obtained prior permission, you may not download an entire issue of a journal or multiple copies of articles, and you may use content in the JSTOR archive only for your personal, non-commercial use. Each copy of any part of a JSTOR transmission must contain the same copyright notice that appears on the screen or printed page of such transmission. American Mathematical Monthly 1s published by Mathematical Association of America. Please contact the publisher for further permissions regarding the use of this work. Publisher contact information may be obtained at http://www.jstor.org/journals/maa.html. American Mathematical Monthly ©1928 Mathematical Association of America JSTOR and the JSTOR logo are trademarks of JSTOR, and are Registered in the U.S. Patent and Trademark Office. For more information on JSTOR contact [email protected]. ©2002 JSTOR http://www. jstor.org/ Sun Nov 24 23:14:57 2002 114 THE MECHANICAL COMBINATION OF LINEAR FORMS [Mar., If to the balance on 1927 business shown in this report, $8,228.66, there be added the bills receivable, $200.00, and there be subtracted the estimated bills payable, $4,760.52, there results an estimated final balance on 1927 business of approximately $3,700, a satisfactory advance in the Association’s resources for the year. W. D. Carrns, Secretary-Treasurer THE MECHANICAL COMBINATION OF LINEAR FORMS By D. H. LEHMER, University of California, Berkeley. The “method of exclusion” introduced by Gauss, although a tentative method, is still one of the most powerful weapons for attacking many prob- lems in the theory of numbers. Perhaps the most familar of such problems is the solution of the congruence «?=D (mod m). The method is also of great use in the problem of representing a number by a given form such as a? — 9, a? + 0, a+ Db?,-+:. Suppose, for instance, we wish to represent a given number N as the dif- ference of two squares. We may choose 5 as an ‘excluding number.” Let N =3(mod 5). We construct the following table a=01234 @’@=01441 (mod 5) @—-N=8=2311 3 But 2 and 3 are non-residues of 5 so that the cases a=0, 1, and 4 (mod 5) are excluded. We have then a=5n+2, 3. Other small prime moduli may be used as excluding numbers with the result that a is restricted to (p+1)/2 values modulo . The problem that now presents itself is the combination of the linear forms thus obtained. If the range of a is large, it is necessary to use many excluding numbers and the labor of combining directly these linear forms is prohibitive. A graphical method has been suggested! to solve this difficulty in which use is made of a table ruled in squares, each cell representing a possible value of a. “Movable strips” are made, the length of each being some excluding number #, and on which impossible values of a modulo p are indi- 1 Kraitchik, Theorie des Nombres (Paris, 1922), Chapter 2. 1928] THE MECHANICAL COMBINATION OF LINEAR FORMS 115 cated by crosses. These strips are moved down the columns of the table and the cells adjacent to the crosses on the strip are then ruled out. As many strips as are necessary are computed and applied until the number of empty cells is reasonably small for actual trial. But even this method has certain disadvantages. In the first place it requires very close attention and much care. Also the strips are short in comparison with the length of the table and have to be shifted frequently, which is a possible source of error. Moreover the method makes it necessary to fix the limit of the table before commencing the work, so that the whole range must be entirely covered before any definite information can be ob- tained. These difficulties are overcome by a machine constructed by the writer for the combination of linear forms. It is the object of this paper to give a brief description of the machine and to exhibit some of the results obtained by it. Here instead of strips we have chains. The number of links in each chain is a convenient multiple of some small prime. In fact the chain lengths are: 64, 27, 25, 49, 22, 26, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, and 67. Each chain hangs in a loop from a sprocket having 10 teeth. All the 19 sprockets are fixed rigidly to a single shaft driven by a motor. The possible values modulo # are indicated by small pins fastened to the appropriate links of the chain (the zero link being indicated by red paint.) Whenever a link provided with a pin arrives at the top of the shaft a small spring with a tungsten point is lifted by the projecting pin. This breaks for the moment the electric contact between the spring and a brass bar running parallel to the shaft. By means of a relay in the circuit, the motor is shut off and the machine stops itself. When several chains are provided with springs the machine will not stop unless all the springs are lifted, so that every time the machine stops it means that a number satisfying all the imposed conditions hasappeared. Thisnumbercanberead directly by means ofarevolution counter connected to the shaft. The shaft revolves 300 r. p. m. so that the machine canvasses 3000 numbers per minute. When all chains are provided with springs a ‘‘solution’”’ occurs once in several hours during which time the machine runs without any attention. The use of the machine is best explained by means of examples. Let us first consider the representation of . WN = (10% + 1)/(104 + 1) = 9999000099990001 = a? — 82 as the difference of two squares. A representation besides a@=(N+1)/2, b=(N—-1)/2 116 THE MECHANICAL COMBINATION OF LINEAR FORMS [Mar., is possible since NV has been shown to be the product of two primes.!_ The factors of: NV are of the form 40n+1. The expansion of the square root of N in a regular continued fraction seems to indicate that, although 21 is a residue of N, 3 and 7 are both non-residues. The assumption that 3 is a non-residue gives the following form for the factors of V: 3n + 2 \ 120” + 41. 40z +1 Let us then write (1) a+b = 120n +41, (2) a—b=120m-+ 41. Multiplying (1) and (2) we get a? — 6? = N = 120°mn + 120-41(m +n) + 41°. Now N=10801 (mod 120°). Therefore 120-41(m-+n) =9120 (mod 1202), or 41(m + n) = 76(mod 120). Solving this congruence we have (3) (m + n) = 116(mod 120). Adding (1) and (2) we get a=60(m+n)+41. Substituting from (3) we get (4) a = 60(120k + 116) + 41 = 7200k + 7001. The range for a is given by the formula 1 N VN <a< s(v + =), where W is the limit to which the number has been searched for factors. In this case? W = 120,000 so that a has the range 99995000 < a < 41662560416 with 13888 << k < 5786466. Now let « =k —13888 so that 0<x<5772578. Then (4) gives (5) a = 7200(#% + 13888) + 7001 = 7200x + 100000601, so that a is restricted to one case in 7200. 1 Bulletin of the American Mathematical Society, vol. 33, p. 336. 2 This limit has been established by Shanks’ table of the number of digits in the repetend of the reciprocal of every prime< 120000. 1928] THE MECHANICAL COMBINATION OF LINEAR FORMS 117 We proceed now to exclude x with small prime moduli. Let us take for example the excluding number 11. We have from (5) a = 6x + 8(mod 11) N = 1(mod 11). We now construct the following table: 2=0123 45 678910 (mod 11) a=6e+8=8394105 0617 2 a=9945 13 0315 4 a@—-N=0?=8 834 0210204 3 Excluding those values of x which correspond to non-residues in the last line, we get the following linear forms for « modulo 11: x= 1lin+ 2,3, 4, 8, 9, 10. Other excluding numbers may be dealt with in like manner. Kraitchik! has given tables of the possible values of a for any N and for excluding numbers $47. The possible values of x can easily be obtained from the tabulated values of a by means of the transformation 1 I L= - a- — Henod p) whenever a = kx + I(mod ). These tables have been recalculated and the errors noted are given at the end of the present paper. In order to serve the needs of the machine these tables have been extended to excluding numbers $67. The use of the tables is to be preferred to the method illustrated by the above example. The calculation is much simpler and the results can easily be checked by symmetry. For in- stance the table for 11 gives in our case a@=1, 2, 4, 7, 9, 10(mod 11). Making the transformation 1 1 t= ra——8 = 2a +6 (mod 11), we get + =8, 10, 3,9, 2,4. (mod 11) as before. We can also make good use of the condition that 7 is a non-residue of NV. The factors of N are then of the form 7n+3, 5, or 6. Since N=2 (mod 7), we have the following two cases to consider. 1 Kraitchik, loc. cit., pp. 187~199. 118 THE MECHANICAL COMBINATION OF LINEAR FORMS [Mar., Case I. a+b=7n+3; a—b=7m+4+3. N = a? — b? = 49mn + 21(m + n) + 9 =9 (mod 72). m+n “. m + n = O(mod 7) ; o=i( V+ 3; a = 3(mod 49). Case II. atb=7n+5; aFb=7m+6. N = 49mn + 7(5m + 6n) + 30 = 9(mod 72). “. Sm + 6n = 4(mod 7); m+n=0, 1,2, 3, 4, 5, 6(mod 7). m+n 11 =7 aa ° ( 2 )+5 a = 7K + 30(mod 49)(K = 0, 1, 2, 3, 4, 5, 6). a = 30, 37, 44, 2, 9, 16, 23(mod 49). Considering both cases we have a = 49n + 2, 3, 9, 16, 23, 30, 37, 44. Transforming to x we get a“ = 49n + 2,9, 16, 23, 25, 30, 37, 44. We have thus restricted « to 8 cases modulo 49 instead of the usual 28 cases. The result is that the machine will run longer between solutions. Linear forms for « were thus calculated for every excluding number $67 and the appropriate links of each chain were supplied with pins. The machine was then set in motion. After running about 2 hours it stopped itself at x = 400453, @ = 2983262201 ; a? — N = 8889854359815374400 = 29815858802 = b? This gives us V = (a—b) (a+b) = 1676321 X 5964848081. . If the entire range had been covered without finding the factors of N, it would have indicated that 3 and 7 were residues contrary to our previous as- sumption. This case could have been taken care of, without changing the posi- tion of the pins, by simply shifting the origin on each chain as explained later. The machine would then have to be set back to zero and another run made. Even if two runs were necessary the consideration of the quadratic character of 3 reduces the number of values of « to 2/9. Another example of the representation by the difference of two squares is furnished by N = 20191210335106439, a large factor of 3!1!+1. Every factor of the number is of the form 111”-+1. Hence, as before, a can be restricted to one case in 111?=12321. Alsoa=4n+2. Consequently we have a =49284k+6550. The range for a is 44935627 <a <10096101675 corresponding to W = 100,000 as set by congruence tables. Hence 1928] THE MECHANICAL COMBINATION OF LINEAR FORMS 119 (5) a@ = 49284x +- 44978200 with 0 < « < 203943. The linear forms for x were calculated as above with the exception of those for the excluding numbers 3 and 37 which are not prime to the modulus 49284. The first of these was computed as follows. The form (5) may be written a = 36x + 34(mod 81), a? = 18x + 22(mod 81), N = 4(mod 81), 6? = 18% + 18(mod 81), r = 2x + 2(mod 9), where r designates all the quadratic residues of 9, which are 0, 1, 4, 7. Putting in these values we obtain «= 9n+1,4, 7,8. The linear forms for 37 were calculated in a similar way. All the linear forms were set on the chains and the machine, after running only 4 seconds, stopped at «=145 giving a = 52124380 6b = 26414781. ‘Therefore V =20191210335106439 = 25709599 x 78539161. If the same problem had been attacked by the “movable strip” method, the entire range would have been excluded before this solution was discovered. The machine was also used to show that the other large factor of 3!1!+1, namely 64326272436179833 is a prime which gives the complete factorisation 311 + 1 = 2? X 7 X 223 X 18427 X 107671 & 25709599 X 56737873 X 78539161 X 64326272436179833. The Sth and 7th of these primes are due to Poulet. We consider next the representation of a number as the sum of two squares. The indeterminate equation x?—1721y?=—1 has for its fundamental solution x = 31738680901536260 y = 76506518214341. We have then x?+1=1721y?. Thus y is a divisor of the sum of two squares and therefore every factor of y is the sum of two squares. We have y = 17 X 4500383424373 = 17 x NV. We propose to represent WV as the sum of two squares. Using 5 as an excluding number we get a=5n+2, 3. To save time we consider the two separate cases a=5x+2 and a=5x+3. Taking the first case we proceed to exclude values of x with all the excluding numbers except 5. The tables constructed for the dif- ference of squares may be used for the sum of squares. For an excluding number ~ 120 THE MECHANICAL COMBINATION OF LINEAR FORMS [Mar., of the form 4”+1 the entries are identical. For the case 4n+3 the entries not tabulated are those desired, with the exception of the pair of entries correspond- ing to b2=0 (mod f), which must be included. The range of a in either case is 0<a</(N/2), 0<a< 1500063, 0 <x < 300013. The machine covered the range for the first case with but a single stop at x = 196113, a@ = 980567, N — a® = 3538871782884. This number is not a square although it is a residue of every prime $67. To consider the second case, in which a=5x+3, no further calculation was necessary. The values of a in each case must be congruent modulo p. That is 5a, + 2 = Sao + 3(mod f) or x1 — x2 = 1/5(mod Pf), for ve = 0, 41:=1/5(mod p). On the second start therefore, instead of setting all the chains on their zero positions we set them on the link corresponding to the value of 1/5 (mod 9). This time the machine stopped only once giving x = 157044, a = 785223, 6 = 1970738. Hence N = (785223)? + (1970738)?. Since this is a unique representation, it follows that V is a prime. This also gives us the complete factorisation of (31738680901536260)?+1. By separating the work into two cases, results were obtained in 2/5 of the time required for a single run. The machine has been used to study the following problem previously con- sidered by Kraitchik,! namely to find the least non-square which is a quadratic residue of all primes. Following Kraitchik, we consider 0 as a non-residue and the number 8 instead of the prime 2. The numbers sought belong to the forms 8% +1 24n + 1. an, a Letting N=24x%+1 we proceed to exclude values of « with moduli=5. To obtain the necessary linear forms we transform a table of residues by means of the relation x=(r—1)/24 (mod p), where r represents the residues of p. All the chains were supplied with pins before starting. To start with, the chain for 5 was provided with a spring and the machine was set in motion. The first non-square solution obtained was 241. Then the next prime was introduced by setting on the spring of the chain for 7. The machine was then run to the first non-square solution after which the spring for the prime 11 was put on, 1 Recherches sur la Théorie des Nombres (Paris, 1924), pp. 41-46. 1928] THE MECHANICAL COMBINATION OF LINEAR FORMS 121 etc. The squares appearing as solutions are of course squares of primes or products of primes >p. These squares were predicted in advance so as to avoid unnecessary reading of the machine. The work was carried up to p=61. The results are summarized in the following table, which gives the least non- square JV, that is a residue of all primes Sp. Ns=17 Prime Ny=18001 47383 Na =3206641 6434987 N; =73 Prime Nig=53881 Prime Ng =3818929 Prime — Ns=241 Prime No3=87481 Prime Na =9257329 Prime N; =1009 Prime Nog=117049 671747 N3 = 22000801 Prime ¢ Nu=2641 19X139 N3,=515761 Prime Ng =48473881 Prime It is seen that most of the V’s are primes. If NV, is a prime it has for residues all the primes <p and also—1. If it is composite there existssome prime <p which is a non-residue of an even number of factors of NV. The interesting case of Nss=Na is the first of its kind. . The above results confirm and extend the work of Kraitchik. He used the movable strip method with a table having 180 columns and 84 lines to carry the work to Ng; A full account of his work is given in his book. A few errors are to be noted which however do not happen to influence the final results. It should be pointed out that to extend Kraitchik’s work by his method would imply the construction of an entirely new table the size of which must be determined in advance. Using the machine the work may be extended in- definitely and is complete as far as it goes. ERRORS IN KRAITCHIK’S TABLE III. Théorie des Nombres, pp. 190-9 p N for read 31 5 a=8 a=11 31 5 t= il t= 8 47 6 t = 10 t= il 47 34 t = 19 t = 22 Since writing the above, the author’s attention has been directed to Kraitchick’s new second volume (Théorie des Nombres, vol. 2, Paris, 1926) which contains tables of a (mod p) for p67. The above errors have been corrected. Only two new error, appear, namely: p N for read 59 23 x=14 x=15 59 44 x=14 x=17