Skip to main content

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

See other formats

282                  HISTORY OF THE THEORY OF NUMBERS.               [CHAP.X
Let S'(ri) be the sum of the odd divisors of n, and Cn be the number of all combinations without repetitions with the sum n, so that C7 = 5.   Then
D(ri) = -D(n-l) -D(n-3)-D(n-6)- ...,   D(n) = /S'(n) -S(n). A complicated recursion formula for r(n)is derived from
log{(l-aO(l-')*(!-a8)*. ..}==- -r(n)of.
n* in-Complicated recursion formulas are found for the number of integers <m not factors of m, and for the sum of these integers.   A recursion formula for the sum sr(ri) of the divisors ^r of n is obtained by expanding
log {l-z)(l-z2).. .(1-af)} = - S isr(n)a;n.
Jacobi16 proved (1).
Dirichlet17 obtained approximations to T(n). An integer s^n occurs in as many terms of this sum as there are multiples of s among 1, 2,..., n. The number of these multiples is [n/s], the greatest integer ^n/s. Hence
This sum is approximately the product of n by
Hence T(ri) is of the same order of magnitude as n log n.
Let Ai be the least integer gz^/n and set ?==[n//i].   Then if 0(2) is any function and G(x) =0(1) +0(2) + . . .
s of r5
.i   LLs
In particular, if 0(s) = 1,
Giving to [n/s] the approximation n/s, we see that (7)                             T(rc)=n log
where c is of the same order of magnitude as Vn.
Let p(n) be the number of distinct prime factors >1 of n.   Then 2p(n) is the number of ways of factoring n into two relatively prime factors, taking
"Jour, fur Math., 32, 1846, 164; 37, 1848, 67, 73.
"Abhand. Ak. Wiss. Berlin, 1849, Math., 69-83; Werke, 2, 49-66.   French transl., Jour, de Math., (2), 1, 1856, 353-370.