9.2   Computing phi(n): A Special Case

As has become our standard practice, we will work towards a general solution to our problem by starting with special cases that are easier to tackle. In this section, we consider the values of phi(n) when n is a power of a prime.

Research Question 1

Find a formula for phi(p), where p is prime.

Research Question 2

Find a formula for phi(pa), where p is a prime and a is a positive integer.

Hint: You may find it easier to count the number of m <= pa such that gcd(mpa) > 1, and subtract this from n = pa.

Section 9.1 | Section 9.2 | Section 9.3 | Section 9.4

Chapter 9 | DNT Table of Contents

Copyright © 2001 by W. H. Freeman and Company