116 6. Integers, Divisors, and Primes
Finally, the numbers divisible by all of 2, 3, 5 are precisely those that are
divisible by 30; so there are
1200
30
numbers divisible by all of 2, 3, 5.Now with these data, we can use inclusion–exclusion to compute the
number we are looking for:
1200 −
(
1200
2
+
1200
3
+
1200
5
)
+
1200
2 · 3
+
1200
2 · 5
+
1200
3 · 5
−
1200
2 · 3 · 5
= 320.
If we pull out 1200 from the left-hand side of the above equality, what
remains can be transformed into a nice product form (check the calcula-
tions!):
1200 ·
(
1 −
1
2
−
1
3
−
1
5
+
1
2 · 3
+
1
2 · 5
+
1
3 · 5
−
1
2 · 3 · 5
)
= 1200·
(
1 −
1
2
)
·
(
1 −
1
3
)
·
(
1 −
1
5
)
.
Letnbe a natural number. We denote byφ(n) the number of those
numbers that are not larger thannand are relatively prime ton(we used
here “not larger,” instead of “smaller,” which has significance only ifn=1,
since this is the only case when the number itself is relative prime to itself;
soφ(1) = 1). Primes, of course, have the most numbers relatively prime to
them: Ifpis a prime, then every smaller positive integer is counted inφ(p),
soφ(p)=p−1. In general, the numberφ(n) can be computed as we did
in the concrete case above:ifp 1 ,p 2 ,...,prare the different prime factors
ofn, then
φ(n)=n·(
1 −
1
p 1)
·
(
1 −
1
p 2)
···
(
1 −
1
pr)
. (6.7)
The proof follows the calculations above, and is given as Exercise 6.9.2.
6.9.2Prove (6.7).6.9.3Letnbe a natural number. We computeφ(d) of every divisordofn, then
add up all these numbers. What is the sum? (Experiment, formulate a conjecture,
and prove it.)
6.9.4We add up all the positive integers smaller thannand relatively prime
ton. What do we get?
6.9.5Prove the following extension of Fermat’s Theorem: If gcd(a, b) = 1, then
aφ(b)−1 is divisible byb.
[Hint: Generalize the proof of Fermat’s Theorem in Exercise 6.5.4.]