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

32

THEORY OF NUMBERS

are in some order the numbers o, I, 2,..., v-i. The number of integers in this set prime to v is evidently 0(v).
Hence it follows that in any column of the array (A) in which
the numbers are prime to u there are just #(v) numbers which
are prime to v. That is, in this column there are just ~(v)
numbers which are prime to yv. But there are q(A) such
columns. Hence the number of integers in the array (A)
prime to yv is ~(u)4(v)).
But from the definition of the 0-function it follows that
the number of integers in the array (A) prime to uv is O(^v).
Hence,
<()= = ~() 4(J),
which is the theorem to be proved.
COROLLARY. In the series of n consecutive terms of an
arithmetical progression the common difference of which is prime
to n, the number of terms prime to n is C(n).
From theorem I we have readily the following more general
result:
II. If mi, m2,...,mk are k positive integers which are
prime each to each, then
0(m1im2... mek) = (mi) p(m2).... (11k).
~ I6. THE INDICATOR OF ANY POSITIVE INTEGER
From the results of ~~ 4 and 15 we have an immediate
proof of the following fundamental theorem:
If m=plalp2a2... ipn, where pi, p2,..., pn are different primes and al, a2,..., an are positive integers, then
~(m)=m - )( ) (. ).
For,
~(m) = <(plai) 0(p2ca,)... (pan)
pai) ( p2 I ( I n p
=m I- — ) I ---
pi p9 \ pn