Section 9.3: Computing phi(n): The General Case

9.3 Computing (n): The General Case

In order to compute (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
(m·n) = (m)·(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
(mn) = (m) (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 (n), where n = p^aq^b, 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 (n), where
n = ,
p₁, p₂, . . . , p_k are distinct primes, and a₁, a₂, . . . , a_k are positive integers.

Exercise 2

Use your formula from Research Question 5 to compute (10²⁰), 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