We begin here by recalling that the function

_{}(n) counts the number of integersmsuch that 1mnand gcd(m,n) = 1. In the Prelab section of this chapter, you computed_{}(n) for a few different values ofnby systematically checking eachmsuch that 1mn, and counting how many satisfied gcd(m,n) = 1. Clicking on "First phi" in the applet below will automatically do the same thing. Try it out; click on "First phi" to evaluate_{}(20).

The output tells us that

_{}(20) = 8. It also tells you how long it takes to perform the computation. Let's try out "First phi" on a larger number:

This one takes a bit longer, which shouldn't be surprising, because there are more values of

mto check. The applet has a second built-in function called "Fast phi" that also computes_{}(n), but does so using a method different from "First phi". Try out both "First phi" and "Fast phi" below to compare the computation times.

Clearly "Fast phi" is faster than "First phi". (Could we possibly expect a function called "Fast phi" to be

slower?) The reason is that "Fast phi" uses an algorithm that is more efficient than the one used in "First phi". One goal for this chapter is to find this more efficient method for computing_{}(n).

## Exercise 1

(a) Use the applet to determine the time required to compute

_{}(10^{4}) using "First phi".

(b) On the basis of the results of part (a), extrapolate the number of years required for "First phi" to compute_{}(10^{20}). (For simplicity, assume that all years have 365 days.)

(c) Use the applet to determine how long it takes "Fast phi" to compute_{}(10^{20}).

Section 9.1 | Section 9.2 | Section 9.3 | Section 9.4

Copyright © 2001 by W. H. Freeman and Company