History Of The Theory Of Numbers - I

138 HlSTOKY OF THE THEORY OF NUMBERS. [CHAP. V
(k<ri). Thus pkn\ = 1 or 0 according as k and n are relatively prime or not. Hence
<£(n)«S \Pkn\, <t>M=%k\Pkn\,
&=1 k=l
where <fo(n) is the sum of the integers ^n and prime to n.
R. Remak112 proved Maillet's93 theorem without using Tchebychefs.
E. Landau113 proved (5), Wolfskehl's91 theorem and Maillet's93 generalization.
C. Orlandi114 proved that, if x ranges over all the positive integers for which [m/x] is odd, then S<£(z) = (w/2)2 for m even (Cesaro, p. 144 of this History), while Sty (a) =k2 for m = 2k — 1.
A. Axer115 considered the system (P) of all integers relatively prime to the product P of a finite number of given primes and obtained formulas and asymptotic theorems concerning the number of integers ^x of (P) which are prime to x. Application is made to the probability that two numbers ^ n of (P) are relatively prime and to the asymptotic values of the number (i) of positive irreducible fractions with numerator and denominator in (P) and ^n and (n) of regular continued fractions representing positive fractions in (P) with numerator and denominator ^ n.
G. A. Miller116 defined the order of a modulo m to be the least positive integer b such that a&=0 (mod m). If pa is the highest power of a prime p dividing m, the numbers :gra whose orders are powers of p are km/pa (/c = l, 2, . . ., pa}. Hence S^-m/p^ (/ct-=l,. . ., pfi) form a complete set of residues modulo m=Hpi°'i. If the orders of two integers are relatively prime, the order of their sum is congruent modulo m to the product of their orders. But the number of integers ^m whose orders equal m is <£(m). Hence ^(Hpa) =H(t>(pCL). Since all numbers ^m whose orders divide d, a divisor of m, are multiples of m/d, there are exactly d numbers ^m whose orders divide d, and <j>(d) of them are of order d. Hence
S. Composto117 employed distinct primes m, n, r, and the v~<$>(mri) integers plt. . ., pv prime to mn and ^ mn, and proved that
pi? Pi+mn, pi+2mn,. . ., pH-(r-l)mn (i = l,...,v)
include all and only the numbers rp1} . . . , rpp and the numbers not exceeding and prime to mnr. Hence 4>(mnr) =4>(mn)-(r — 1). A like theorem is proved for two primes and stated for. any number of primes. [The proof is essentially Euler's1 proof of (1) for the case in which B is a prime not dividing a product A of distinct primes.] Next, if d is a prime factor of n, the integers not exceeding and prime to dn are the numbers rg n and prime to n, together with the integers obtained by adding to each of them n, 2n, . . . ,
112Archiv Math. Phys., (3), 15, 1909, 186-193.
113Handbuch. . .Verteilung der Primzahlen, I, 1909, 67-9, 229-234.
114Periodico di Mat., 24, 1909, 176-8.
115Monatshefte Math. Phys., 22, 1911, 3-25.
118Amer. Math. Monthly, 18, 1911, 204-9.