Section 2.4 Number Theory
151
φ(n) = n − a
n
p 1
+
n
p 2
+
n
p 3
−
n
p 1 p 2
−
n
p 2 p 3
−
n
p 1 p 3
+
n
p 1 p 2 p 3
b
= na1 −
1
p 1
−
1
p 2
−
1
p 3
+
1
p 1 p 2
+
1
p 2 p 3
+
1
p 1 p 3
−
1
p 1 p 2 p 3
b
= na
p 1 p 2 p 3 − p 2 p 3 − p 1 p 3 − p 1 p 2 + p 3 + p 1 + p 2 − 1
p 1 p 2 p 3
b
(adding
fractions)
= na
( p 1 − 1)( p 2 − 1)( p 3 − 1)
p 1 p 2 p 3
b
(check this by multiplying out the
numerator)
=
n
p 1 p 2 p 3
( p 1 − 1)( p 2 − 1)( p 3 − 1)
= p
m 1 −1
1
p
m 2 −1
2
p
m 3 −1
3
φ(p 1 )φ(p 2 )φ(p 3 )
(1)
Equation (1) expresses φ(n) in terms of the Euler phi function of its prime factors,
which are known to us (see Practice 16).
Equation (1) in Example 34 gives the formula for φ(n) where n has 3 distinct
prime factors. It is easy to extend this equation to the more general case where n
has an arbitrary number of prime factors. If
n = p
m 1
1 p
m 2
2
c p
m k
k
then
φ(n) = p
m 1 −1
1
p
m 2 −1
2
c p
m k −1
k
3φ(p 1 )φ(p 2 ) c φ(p k )4
(2)
eXAMPLe 36
For n = 133848 = 2
3 # 3
2 # 11 # 13
2
,
φ(n) = 2
2 # 3 # 13 3φ(2)φ(3)φ(11)φ(13)4 = 4 # 3 # 13 31 # 2 # 10 # 124 = 37440
PrACTiCe 17 For n = 3
4 # 5 # 7
2
, compute φ(n).
■
Equation (2) requires that we know the prime factorization of n, so it does not
avoid the difficulty we noted earlier of factoring large values of n.