Skip to main content
CHAP, xiv] METHODS OP FACTORING. 363
Then the divisors of A are included among these linear forms. When V/bA is converted into a continued fraction, let (vlcA +/)/D be a complete quotient, and p/q the corresponding convergent. Then =*=D=p2—fcAg2, so that the divisors of A are divisors of p2=FJD.
C. F. Gauss47 stated that the 65 idoneal numbers n of Euler and no other numbers have the two properties that all classes of quadratic forms of determinant —n are ambiguous and that any two forms in the same genus (Geschlecht) are both properly and improperly equivalent.
Gauss48 gave a method of factoring a number M based on the determination of various small quadratic residues of M.
Gauss49 gave a second method of factoring M based on the finding of representations of M by forms £2+D, where D is idoneal.
F. Minding50 gave an exposition of the method of Legendre 46
P. L. Tchebychef81 gave a rapid process to find many forms rf^ay* which represent a given number A or a multiple of A. Then a table of the linear forms of the divisors of x2=±= ay2 serves to limit the possible factors of A.
Tchebychef52 gave theorems on the limits between which lie at least one set of integral solutions of x2—Dy2 =^N. If there are two sets of solutions within the limits, N is composite. There are given various tests for primality by use of quadratic forms.
C. F. Gauss63 left posthumous tables to facilitate factoring by use of his49 second method.
F. Grube64 criticized and completed certain of Euler's proofs relating to idoneal numbers, here called Euler numbers. While Gauss47 said it is easy to prove Euler's43 criterion for idoneal numbers, Grube could prove only the following modification: Let 0 be the set of numbers Z)+n2^4Z> in which n is prime to D. According as all or not all numbers of 0 are of the form q, 2q, q2, 2X (q a prime), D is or is not an idoneal number.
E. Lucas56 proved that if p is a prime and k is a positive integer, and p = x2+ky2, then p^x2-}-ky2 for values x\y y\ distinct from =*=#, =±=y.
P. Seelhoff66 made use of 170 determinants (including the 65 idoneal numbers of Euler and certain others of Legendre), such that every reduced form in the principal genus is of the type ax2+by2. To factor N seek among the numbers m of which N is a quadratic residue several values
<7Dieq. Arith., 1801, Art. 303. "Ibid., Arts. 329-332. "Ibid., Arts. 333-4.
BOAnfangsgriinde der HSheren Arith., 1832, 185-7.
"Theorie der Congruenzen (in Russian), 1849; German transl. by H. Schapira, 1889, Ch. 8, pp. 281-292.