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

24

THEORY OF NUMBERS

EXERCISES
I. Any positive integer can be represented as an aggregate of different powers
of 3, the terms in the aggregate being combined by the signs + and - appropriately chosen.
2. Let m and n be two positive integers of which n is the smaller and suppose
that 2lan<2;+1. By means of the representation of in and n in the scale of
2 prove that the number of divisions to be effected in finding the greatest common
divisor of m and n by the Euclidian algorithm does not exceed 2k.
~ 12. HIGHEST POWER OF A PRIME p CONTAINED IN n!.
Let n be any positive integer and p any prime number not
greater than n. We inquire as to what is the highest power
pv of the prime p contained in n!.
In solving this problem we shall find it convenient to employ
the notation
[rj
M
to denote the greatest integer a such that asr. With this
notation it is evident that we have
and more generally
L p1 \ 1
P3 pi+i
If now we use H{x} to denote the index of the highest power
of p contained in an integer x, it is clear that we have
H{n}e =H p2p 3p p f Pr
since only multiples of p contain the factor p. Hence!} I +H I2...