You are about to erase your work on this activity. Are you sure you want to do this?

Updated Version Available

There is an updated version of this activity. If you update to the most recent version of this activity, then your current progress on this activity will be erased. Regardless, your record of completion will remain. How would you like to proceed?

Mathematical Expression Editor

We present a formula for Euler’s function.

Relatively Prime Two natural numbers and are called relatively prime if their
greatest common divisor is 1, i.e.,

example 1 The numbers 64 and 81 are relatively prime since the only natural number
that divides evenly into both is 1, i.e., .

(problem 1a) List all pairs that are relatively prime from among the numbers 12, 14,
15, 25 and 45

(problem 1b) Explain why any two successive natural numbers are relatively
prime.

(problem 1c) Explain why any two distinct prime numbers are relatively
prime.

(problem 1d) Which natural numbers are relatively prime to themselves?

Fundamental Theorem of Arithmetic Every natural number greater than 1 has a
unique prime factorization, i.e., for , there exists a unique list of distinct primes and
a unique list of positive integers such that

example 2 Find the prime factorization of 2345. Since the number 2345 ends in 5, it must be divisible by 5. Hence . Now note that
469 is divisible by 7, and we have . Since 47 is prime, this is the unique prime
factorization of 2345.

(problem 2) Find the prime factorizations of 1000, 1111, and 43125.

Euler’s function For each natural number , we define Euler’s function (sometimes
called the totient function) to be the number of natural numbers less than which are
relatively prime to .

example 3 Find . Among the natural numbers less than 10 the following are relatively prime to 10:

Since there are 4 such numbers, .

(problem 3a) Find and .

(problem 3b) Find a formula for any prime .

We now state the main proposition of this section, whose proof utilizes the
Inclusion-Exclusion Principle.

Formula for Euler’s function Let be a natural number with prime factorization .
Then

Proof

If is a natural number less than which is relatively prime to , then
none of the primes will divide . For each , define to be the subset of consisting
of the multiples of the prime . Then

Now, we use the Inclusion-Exclusion Principle to compute :

Euler’s function is multiplicative, i.e., if and are relatively prime, then

Proof

Let the prime factorizations of and be Since and are relatively
prime, the prime factorization of is given by According to the proposition,
and It is now clear that .

example 4 Use the proposition to compute and and then use the corollary to
compute . Since , the proposition gives and since , the proposition gives Finally, since , the
corollary gives

(problem 4a) Use the proposition to compute and and then use the corollary to
compute .

(problem 4b) Use the proposition to establish a formula for where is any prime and
is a positive integer.

The proof of the proposition uses a factorization theorem. We explore this theorem in
the next example and problem.

example 5 Multiply and use this to validate the factorization in the last
step of the proof of the proposition in the case that has 3 distinct prime
factors. The FPC tells us that there will be terms. Further, we can group these terms
according to how many of the variables are present. We have Referring back to the
proof of the proposition, suppose had three distinct prime factors, . Then the
Inclusion-Exclusion Principle gives If we expand these sums, we obtain Noting that
the expression in the brackets has the same form as the expansion of with and , we
have

(problem 5a) Multiply and use this to validate the factorization in the last
step of the proof of the proposition in the case that has 4 distinct prime
factors.

(problem 5b) Conjecture the factorization formula for

(problem 5c) Conjecture the factorization formula for