Reference / Paper · 1933
Some New Factorizations of 2ⁿ ± 1 (Bull. AMS 39, 105–108)
Factorizations found with the photoelectric gear sieve, including the factoring of 2⁹³+1.
Reference / Paper · 1933
Factorizations found with the photoelectric gear sieve, including the factoring of 2⁹³+1.
NEW FACTORIZATIONS 1933-1 105 SOME N E W FACTORIZATIONS OF 2 » ± 1 BY D. H. LEHMER 1. Introduction. The purpose of this note is to announce five new factorizations of 2n± 1. The results are due directly and indirectly to the writer's new number theoretic machine.* In fact the large primes quoted below would have remained undiscovered by the writer had he not been in possession of the means of factoring numbers of this size without difficulty. The actual factorizations quoted below are the result of a month's experiment with the machine. As a matter of fact the machine ran only a few hours altogether. When some permanent location has been found for the apparatus, it is hoped to consider much more difficult problems. 2. Theorem f or Large Primes. We begin with the large primes. These primes were identified with the help of the following theorem, f the integer N divides aN~~l — 1, but is prime to aw-v/p — lf p a prime, then all the factors of N are of the form T H E O R E M A. If px + 1. If a large enough prime factor p of N— 1 is known, this theorem so restricts the factors of N, that the primality of N follows almost at once. 3. Factorization of 273 + l. The number N in this case is 273+ 1 N = — = 1795 91803 87410 70627. 31753 It was found that N—l is divisible by £ = 811, and that the hypothesis of Theorem A is satisfied for a —3. Hence every factor of iVis of the form 811x + 1 , as well as 73x + l and 8# + l, 3. Writing N = a2 — b2, we deduce at once a = 28039961672^ + 244363342366. * This Bulletin, vol. 38 (1932), p. 635. t This theorem is a special case of Theorem 3, of the writer's article published in this Bulletin, vol. 33 (1932), p. 331. 106 D. H. LEHMER [February, Since the smallest factor of N is known to exceed 300000, we find a g 2993196881235, so that k ^ 107. These few values of k are easily disposed of using small moduli ^ 1 9 . Hence N is a prime and we have 2^3+ l = 3-1753.1795 91803 87410 70627. 4. Factorization of 285— 1. The number N under consideration here is 285 - 1 N = = 9520 97280 63337 58431. ( 2 17 __ 1 ) ( 2 5 _ 1) Here iV—1 is divisible* by £ = 257. The hypothesis of Theorem A is shown to be satisfied with a = 3, and the primality of N follows easily as before. Hence 285 _ i = 31-131071-9520 97280 63337 58431. 5. Factorization of 295 + l. The number N in this case is (295 + 1)(2 + 1) N = — = 3011 34747 96142 49131. (219 + 1)(25 + 1)(2281) It was found that N divides 3ivr~1 — 1, but no large prime factor of N—l was immediately available. In fact N - 1 = 2-3-5-19-5 28306 57537 09209. It thus became necessary to examine the large factor M of N— 1. By expanding M112 in a regular continued fraction it was found that — 7 is a quadratic residue of M. Hence if M is composite we may expect at least two representations of M by the form x2 + 7y2. The machine gave them in less than half an hour as follows : N = 409234512 + 7-227041122 = 668555392 + 7-107796282. This gives us the decomposition M = 59957-88114244437. This last factor we proved to be a prime by applying Theorem * One may easily show in general that any prime factor of ap~l — \ not dividing a « - l , divides [ ( a ^ - l ) ( a - l ) ] / [ ( a ^ - l ) ( a « - l ) ] - l . NEW FACTORIZATIONS 1933-1 107 A using the factor p = 2489947 of 88114244436. Armed with this large factor of N—l, the application of Theorem A to N was soon completed, and it resulted t h a t N is a prime. Hence 295+ i = 3 . H . 2 2 8 1 174763-3011 34747 96142 49131. This proof for primality is a positive proof, although it may seem round about. The machine could have been easily set to search directly for the factors of N, but its failure to find a factor might not have been acceptable to the reader as a proof of primality. 6. Factorization of 293 + l. The number under discussion here is N= ( 2 9 3 + l ) (:2 + l) ^ = 1537 22867 20933 01419. (231+1)(23+1) Since each factor of N is of the form 93x + l and 8x + l, 3 we find easily that if N = a2 — b2, then a is of the form 69192& + 1239854518. The smallest factor of N exceeds 300000 so that a g 2562047936822, or k ^ 37010176. The machine was set to exclude values of k. I t ran only a few seconds, and delivered the value £ = 6886. This gives us a = 1716310630, and 6 = 1186799691. Hence N = 529510939-2903110321. It is easily seen that both factors are primes, hence 2 9 3 + 1 = 32-529510939-715827883-2903110321. 7. Factorization of 2 79 — 1. We are concerned in this case with N = (279 - l)/2687 = 2 24958 286426 02584 99201. Since the factors of N are of the forms 79x + l, Sx± 1, it follows that if N = a2 — b2, a will have the forms a = 6241a; + 159, 3x + 0, 512* ± 63, 97, 159, 191. Combining these forms w e get a = 9586176& + 159, 1610337, 4793247, 6403425, 6590655, 7002561, 8987199, 9399105. 108 JOHN WILLIAMSON [February, Since a^3749304739l7097, we have in each case £^39111579. Thus the problem of representing N as the difference of squares was split into 8 parts. The first two parts were covered by the machine without any result. On the third run, however, the machine stopped almost at once at x = 58088. This gives a = 556846584735, b = 556644555032. Hence we have the factorization 279 - 1 = 2687-202029703-1113491139767. It is not difficult to show that the factors are primes. This is the 13th composite Mersenne number to be completely factored. The a u t h o r s recent report* on Mersenne numbers should be changed accordingly. PASADENA, CALIFORNIA M A T R I C E S WHOSE sTH C O M P O U N D S A R E EQUAL BY JOHN WILLIAMSON If A is a matrix of m rows and n columns and s is any positive integer less than or equal to the smaller of n and m, from A can be formed a new matrix As of mCs rows and nCs columns, the elements in the tth row of As being the nCs determinants of order s that can be formed from the /ith, • • • , / s th rows of A, and the elements in the tth column being the mCs determinants of order s that can be formed from the hth, • • • , / s th columns of A. The matrix As, so defined, is called the sth compound matrix of A. In the following note we discuss the necessary and sufficient conditions under which the sth compounds of two matrices are equal. We shall require the following lemmas. LEMMA I. The rank of the sth compound of a matrix A, whose rank is r, is rCs if r^s and is zero if s>r.] * This Bulletin, vol. 38 (1932), p. 384. Dr. N. G. W. H. Beeger has kindly called my attention to the fact that 2233 —1 has two known prime factors and should be classified accordingly. f Cullis, Matrices and Determinoids, vol. 1, p. 289.