Skip to main content

Full text of "History Of The Theory Of Numbers - I"

See other formats

CHAP, xiv]                      METHODS or FACTORING.                              359
Then 2an+rc2-r = s2 and m = (a+ri)2-s2. The method is the more rapid the smaller the difference of the two factors.
M. Neumann13 proved that this process of adding terms leads finally to a square and hence to factors, one of which may be 1.
F. W. Lawrence14 denoted the sum of the two factors of n by 2a and the difference by 26, whence n = a262. Let q be the remainder obtained by dividing n by a chosen prime p, and write down the pairs of numbers <p such that the product of two of a pair is congruent to q modulo p. If p = 7, g = 3, the pairs are 1 and 3, 2 and 5, 4 and 6, whence 2a=4, 0 or 3 (mod 7). Using various primes p and their powers, we get limitations on a which together determine a. The work may be done with stencils. The method was used by Lawrence18 to show that five large numbers are primes, including 10,11 and 12 place factors of 323-l, 1029-1,1025-1, respectively. The same examples were treated by other methods by D. Biddle.16
A. Cunningham17 remarked that in computing by Busk's method a k for which (s+k)2N is a square, we may use the method of Lawrence, just described, to limit greatly the number of possible forms of k.
F. J. Vaes18 expressed N in the form a2b2 by use of the square a2 just >N and then increasing a by 1, 2,..., and gave (pp. 501-8) an abbreviation of the method. He strongly recommended the method of remainders (p. 425): If p is a factor ofG=h2- g2, and if g = (G -1)/2 has the remainder r when divided by p, then h  (G+l)/2 must have the remainder r+1, so that pis a factor of 2r+l^G. For example, let G = 80047, whence
0 = 2002+23 = 201-199+24 = 202-198+27,....
For r = 24, 27, -32,... we see that 2r+l is not a multiple of 201, 202,... until we reach 0 = 209-191+p, p = 104, 2p+l=209. Thus 209 divides G.
P. F. Teilhet19 wrote N = a2-b in the form (a+fc)2-P, where P = &2 +2afc+6. Give to k successive values 1, 2,... (by additions to P), until P becomes a square v2. To abbreviate consider the residues of P for small prime moduli.
E. Lebon20 proceeded as had Teilhet19 and then set f=a+kv.   Then
and we examine primes /< a to see if k is an integer.
M. Kraitchik21 would express a given odd number A in the form y2x2 by use of various moduli p. Let A=r (mod p) and let ait..., an be the
13Zeitschrift Math. Naturw. Unterricht, 27, 1896, 493-5; 28, 1897, 248-251.
"Quar. Jour. Math., 28, 1896, 285-311.   French transl., Sphinx-Oedipe, 5, 1910, 98-121, with
an addition by Lawrence on g* +1.
16Proc. Lond. Math. Soc., 28, 1897, 465-475.   French transl., Sphinx-Oedipe, 5, 1910, 130-6. "Math. Quest. Educat. Times, 71, 1899, 113-4; cf. 93-99. "Ibid., 69, 1898, 111. 18Proc. Sect. Sciences Akad. Wetenschappen Amsterdam, 4, 1902, 326-336, 425-436, 501-8
(English); Verslagen Ak. Wet., 10, 1901-2, 374-384, 474^486, 623-631 (Dutch). 19L'interm6diaire des math., 12, 1905, 201-2.   Cf. Sphinx-Oedipe, 1906-7, 49-50, 55. 20A8soc. frang. av. sc., 40, 1911, 8-9. 21Sphinx-Oedipe, Nancy, Mai, 1911, nume*ro special, pp. 10-16.