64 CHAPTER 2 Discrete Mathematics
(d) Show that for any positive integer n, φ(n) ≥»
n/2. (Hint:
prove that for every prime power pe, where e is a positive
integer,φ(pe)≥pe/^2 , unlessp= 2 ande= 1. What happens
in this case?)See the footnote.^5- Given the positive integern, and the positive divisord|nshow that
the number of integersksatisfying 1≤k < nwith gcd(k,n) =d
isφ
(n
d). Conclude that
∑
d|n
φ(d) =n,where the above sum is over the positive divisors ofn.- Letq andnbe positive integers. Show that
# of integersm, 1 ≤m < qn
which are relatively prime withn
= qφ(n).- Suppose thatxis a positive integer with x=qn+r, 0 ≤r < n.
Show that
qφ(n)≤
# of integersm, 1 ≤m < x
which are relatively prime withn
≤(q+ 1)φ(n).- Conclude from Exercises 18 and 19 that
xlim→∞Ñ
# of integersm, 1 ≤m < x
which are relatively prime withnéx=
φ(n)
n.
(^5) Euler’sφ-function has an interesting recipe, the proof of which goes somewhat beyond the scope
of these notes (it involves the notion of “inclusion-exclusion”). The formula says that for any integer
n >1,
φ(n) =n
∏
p|n
Å
1 −^1 p
ã
,
where the product is taken over prime divisorspofn. A main ingredient in proving this is the result
of Exercise 17, above. Note that this formula immediately implies thatφ(mn) =φ(m)φ(n) whenm
andnare relatively prime.