370 HlSTOET OF THE THEOBY OF NlJMBEKS. [CHAP. XIV
K. P. Nordlund117 would use the exponent e to which 2 belongs modulo N [Boumakowsky111].. For 2V=91, e = 12 is not a divisor of N— 1, so that N is composite, and we expect the factor 13.
L. E. Dickson118 found the factors of 567=*=1, 2613+1, 3417+1, 5213+1 by an expeditious method. For example, each factor of
is si (mod 14). Let& = (l+14fc)(l+14/c1). Then
Thus k and ki are the roots of a quadratic whose discriminant Q is of the second degree in h. By use of various moduli which are powers of small prunes, the form of h is limited step by step, until finally at most a half dozen values of h remain to be tested ciirectly.
L. E. Dickson119 gave further illustrations of the last method.
J. Schatunovsky120 reduced to a minimum .the number of trials in Gauss'110 method of exclusion, taking the simplest case 7w = l. He gave theorems on the linear forms of the factors of a2-f-D&2, which lead easily to all its odd factors when D is an odd prime.
H. C. Pocklington121 would use Fermat's theorem to tell whether N is prime or composite. Choose an integer x and find the least positive residue of $N~l modulo N} if 5^1, N is composite. But if it be unity, let p be a prime factor (preferably the largest) of N— 1 and contained a times in it. Find the remainder r when xm is divided by N, where m=(N—l)/p. If r/^1, let 5 be the g. c. d. of r— 1 and N. If 5>1, we have a factor of N. If 5 = 1, all prime factors of N are of the form kpa+l. But if r = l, replace m by m/q, where q is any prime factor of m and proceed as before.
D. Biddle1210 made use of various small moduli.
A. G^rardin1216 used various moduli to factor 77073877.
See papers 14, 15, 21, 22, 48, 65.
FACTORING INTO Two NUMBERS 6n=±=l. G. W. Kraft122 noted that 6a+l = (6m+l)(6rc+l) implies
Find which m = 1, 2, 3, ... makes n an integer.
Ed. Bartl123 tested 6-186+5 for a prime factor less than 31, just less than its square root, by noting that 186, 185, 184, 183, 182 are not divisible by 5, 11, 17, 23, 29, respectively; while the last of 7, 13, 19 is a factor.
"'Gdteborgs Kungl. Vetenskaps. Hand!., (4), 1905, VII-VIII, pp. 21-4.
118Amer. Math. Monthly, 15, 1908, 217-222. llflQuar. Jour. Math., 40, 1909, 40-43.
^Der Grosste Geraeinschaftliche Teiler von Algebr. Zahlen z welter Ordnung, Diss. Strassburg, Leipzig, 1912. 121Proc. Cambridge Phil. Soc., 18, 1914-5, 29-30.
"iaMath. Quest. Educat. Times, (2), 25, 1914, 43-6. ^L'enseignement math., 17, 1915, 244-5. mNovi Comm. Ac. Petrop., 3, ad annos 1750-1, 117-8. 123Zur Theorie der Primzahlen, Progr. Mies, Pilsen, 1871.