394 HlSTOEY OF THE THEOKY OF NUMBERS. [CHAP. XVII
prime of which b is a non-residue, and having the form 2mnó1, will divide V. If ft = ó n, where n is a prime 4w4-3, no prune divides V unless it is of the form fcw=*=l, and conversely. The divisors of U are discussed for the case n a power of 2; in particular, of J7 = #4-|-6&£2-|-&2 when nó4.
J. P. M. Binet10 noted that the number of terms of a solution vn, expressed as a function of r*i, r2, ..., of the equation vn+2=*vn+i+rnvn in finite differences is
This equals Un as shown by taking each rn to be unity.
G. Lame*11 used the series of Pisano1 to prove that the number of divisions necessary to find the g. c. d. of two integers by the usual process of division does not exceed five times the number of digits in the smaller integer. Lionnet12 added that the number of divisions does not exceed three times it when no remainder exceeds half the corresponding divisor. See also Serret, Traite* d'Arithme'tique; C. J. D. Hill, Acta Univ. Lundensis, 2, 1865, No. 1;.E. Lucas, Nouv. Corresp. Math., 2, 1876, 202, 214; 4, 1878, 65, and The*orie des Nombres, 1891, 335, Ex. 3; P. Bachmann, Niedere Zahlentheorie, 1902, 116-8; L. Grosschmid, Math.-Naturwiss. Blatter, 8, 1911, 125-7, for an elementary proof by induction; Math. e*s Phys. Lapok, 23, 1914, 5-9; R. D. Carmichael, Theory of Numbers, p. 24, Ex. 2.
H. Siebeck13 considered the recurring series defined by
for a, c relatively prime. By induction,
where j3 = 0 or 1, 7 = (ró 1)/2 or (ró 2)/2, according as r is odd or even;
^-W N2+ . . . +Nmr Nr,
whence Nrm is divisible by Nm. If p and q are relatively prime, Np and Nq are relatively prime and conversely. If p is a prime, 6 = a2+4c, and s = (b/p) is Legendre's symbol, then
Np=s, Np_a=0 (mod p),
so that either Np+i or Np-i is divisible by p.
J. Dienger14 considered the question of the number of terms of the series of Pisano with the same number of digits and the problem to find the rank of a given term.
A. Genocchi15 took a and b to be relatively prime integers and proved that Bmn is divisible by Bm and that the quotient Q has no odd divisor in
"Comptes Rendus Paris, 17, 1843, 563.
"Ibid., 19, 1844, 867-9. Cf. Binet, pp. 937-9.
lsCompl6ment des 616ments d'arithm&ique, 1857, 39-42.
13Jour. fur Math., 33, 1846, 71-6. 14Archiv Math. Phys., 16, 1851, 120-4.
15Annali di Mat., (2), 2, 1868-9, 256-267. Cf. Genocchi22- ".