The theory of numbers, by Robert D. Carmichael ...

ON THE INDICATOR OF AN INTEGER

35

~ I7. SUM OF THE INDICATORS OF THE DIVISORS OF A NUMBER
We shall first prove the following lemma:
Lemma. If d is any divisor of m and m=nd, the number
of integers not greater than m which have with m the greatest common divisor d is ~(n).
Every integer not greater than m and having the divisor
d is contained in the set d, 2d, 3d,..., nd. The number of
these integers which have with m the greatest common divisor
d is evidently the same as the number of integers of the set
I, 2,..., n which are prime to m/d, or n; for ad and m have
or have not the greatest common divisor d according as a is
or is not prime to m/d, -n. Hence the number in question
is ~(n).
From this lemma follows readily the proof of the following
theorem:
If dl, d2,..., dr are the different divisors of in, then
(di) + (d2) +... + ~(dr)= m.
Let us define integers min, mn2,..., m by the relations
7d1 = dim1 = d22.. dm7r.
Now consider the set of m positive integers not greater than
mt, and classify them as follows into r classes. Place in the
first class those integers of the set which have with in the greatest common divisor ml; their number is ~(dl), as may be seen
from the lemma. Place in the second class those integers
of the set which have with m the greatest common divisor m2;
their number is ~(d2). Proceeding in this way throughout,
we place finally in the last class those integers of the set which
have with m the greatest common divisor mnr; their number
is 0(dr). It is evident that every integer in the set falls into
one and into just one of these r classes. Hence the total number in of integers in the set is 0(dl) + (d2) +... +0(dr).
From this the theorem follows immediately.