Math 312 Worksheet - University Of British Columbia -2016 Page 8
ADVERTISEMENT
1
2
3
4
5
6
7
88
PROBLEM 7 (20 points)
Show there is no positive integer n such that φ(n) = 14, where φ is
the Euler φ-function.
Answer: Suppose φ(n) = 14. Thus n > 1 because φ(1) = 1. Let
a
a
n = p
1
. . . p
, a
1 be the prime decomposition of n. Recall that
i
1
k
a
a
1
a
a
φ(p
) = p
(p
1)
and
φ(n) = φ(p
1
) . . . φ(p
).
i
i
i
1
k
From the formula it follows that p 1 14 for each prime p n. That is
a
b
p 1
1, 2, 7, 14 implying p = 2 or 3. Hence n has the form n = 2
3
where a, b
0 are not both 0. From the formula we see that if a > 0
or b > 0 we have respectively
a
a 1
b
b 1
φ(2
) = 2
or
φ(3
) = 3
2.
a
b
Finally, since φ(n) = φ(2
)φ(3
) the previous equalities show that 7
does not divide φ(n). We conclude there is no integer n satisfying
φ(n) = 14.
ADVERTISEMENT
0 votes
Related Articles
Related forms
Related Categories
Parent category: Education