History Of The Theory Of Numbers - I

118 HISTORY OF THE THEORY or NUMBERS. [CHAP, v
where plt . . . , p» are distinct prunes. For a prime p, not dividing y, we have <j> (py) = (p - !)<£ (y) . Take y = pi,p = p2', then
Next, take y~pip2, P=Pz, and use also the last result; thus
and similarly for #(2). When f ranges over the integers < 2? and prime to 2, the numbers j>2+f 0> = 0, 1, . . . , n — 1) give without repetition all the integers <Z and prime to Z. Hence 0(Z) =n^(s), which leads to (2). [Cf. Guil-min,23 Steggall.78]
The proofs of (4) by Gauss5 and Catalan11 are reproduced without references (pp. 87-90). A third proof is given. Set N = aa~b0cy . . ., where a, 5, c, . . . are distinct primes. Consider any divisor e = bdlc*1 ... of N such that e is not divisible by a. Then
Sum for fc = 0, 1, . . . , a; we get aa^>(c). When k ranges over its values and Pi over the values 0, 1, . . ., 0, and yl over the values 0, 1, . . ., 7, etc., ca* ranges over all the divisors d of N. Hence S<£(d) = aa£<£(€)- Similarly, if 6! range over the divisors not divisible by a or 6,
E. Prouhet18 proposed the name indicator and symbol i(N) for ct>(N). He gave Gauss' proof of (1) and Catalan's proof of (4). If 5 is the product of the distinct prime factors common to a and 6,
As a generalization, let 5; be the product of the distinct primes common to i of the numbers a1} . . ., an; then
Friderico Arndt19 proved (1) by showing that, if x ranges over the integers < A and prime to A, while y ranges over the integers < B and prime to B, then Ay+Bx gives only incongruent residues modulo AB, each prime to AB, and they include every integer < AB and prime to AB. [Crelle's17 first theorem for n = 2.]
V. A. Lebesgue20 used Euler's2 argument to show that there are
p-q...k
integers < AT and prime to p, q, . . . , k, the latter being certain prime divisors of N [Legendre,4 Minding9].
18Nouv. Ann. Math., 4, 1845, 75-80. "Jour, fur Math., 31, 1846, 246-8. 20Nouv. Ann. Math., 8, 1849, 347.