9.3   Computing phi(n): The General Case

In order to compute phi(n) for values of n that are more complicated than prime powers, we would like to develop a means for breaking the general computation into several simpler computations. One way to proceed is to determine combinations of m and n for which the statement

phi(m·n) = phi(mphi(n)

is true. This leads us directly to the next Research Question.

Research Question 3

Find a condition for pairs of integers m and n which guarantees that

phi(mn) = phi(m) phi(n).

Note: The proof of your conjecture (assuming you find the conjecture we are looking for) will be considered on your homework assignment. You can provide a proof with the lab report if you have one, but this is not required. However, since you are not mandated to include a proof for your conjecture, you should provide lots of numerical data to support your claim.

Research Question 4

Use your conjectures from Research Questions 2 and 3 to assist in finding a formula for phi(n), where n = paqb, p and q are distinct primes, and a and b are positive integers.

We're almost there. Here's the last step:

Research Question 5

Find a formula for phi(n), where

n = piai,

p1, p2, . . . , pk are distinct primes, and a1, a2, . . . , ak are positive integers.

Exercise 2

Use your formula from Research Question 5 to compute phi(1020), explaining the steps. Compare the result with your answer to Exercise 1(c).

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