## Euler's phi function

Euler's totient- or -function is needed for the description of the RSA cryptosystem given later.

Definition 1.4.9   The number of integers which are relatively prime to is denoted , called the Euler -function or the Euler totient function.

Example 1.4.10 (1)   , , and more generally, any two distinct primes are always relatively prime.

(2) If is any prime then each of the integers is relatively prime to . Therefore,

where is any prime number.

(3) We have the following table of values of for small :

 1 2 3 4 5 6 7 8 9 10 1 1 2 2 4 2 6 4 6 4

Corollary 1.4.11   Let and be integers. is relatively prime to if and only if there are integers such that .

proof: (only if) This is a special case of the Euclidean algorithm (Theorem 1.4.3).

(if) If and then , so . This forces , so .

The fastest way to compute is to use the formula , assuming one can factor into relatively prime factors and . The proof of this fact and more details on the Euler -function will be given later in §1.6.

Exercise 1.4.12   Find integers , , and for which , where

(a) and ,

(b) and ,

(c) and .

Exercise 1.4.13 (a)   Let

(b) Let

(c) Let

Use Theorem 1.4.3 to find an such that .

Exercise 1.4.14   Lisa paid $133.98 for some$ 1.29 pens and $2.49 notebooks. She didn't buy 100 pens and 2 notebooks, even though this adds up to the right amount. How many of each did she buy? Exercise 1.4.15 Laurel owes Hardy$10. Neither has any cash but Laurel has 14 DVD players which he values at $185 each. He suggests paying his debt with DVD players, Hardy making change by giving Laurel some CD players at$ 110 each. Is this possible? If so, how?

Exercise 1.4.16   Laurel still owes Hardy $10. Hardy says his CD players are worth$ 111 dollars. Is the deal still possible? If so, how?

Exercise 1.4.17   Laurel still owes Hardy $10. Hardy says his CD players are worth$ 111 dollars. Laurel says he will value his DVD players at $184 if Hardy will take$ 110 for his CD players. Is the deal still possible? If so, how?

Exercise 1.4.18   Compute , , .

Exercise 1.4.19 (a)   Write down the elements of the set

closest to (and including) 0.

(b) Show that the set is closed under addition and multiplication 1.3.

(c) Use part (a) to find an such that . (You know such an exists by the above Lemma 1.4.2.)

Exercise 1.4.20 (a)   Let .

(b) Let .

Show that is an ideal.

Exercise 1.4.21   Prove or disprove: For , is a prime if and only if .

Exercise 1.4.22   Show that has no integer solutions.

Exercise 1.4.23   Find all the integers and which satisfy both and .

Exercise 1.4.24   Suppose that you have a collection of 144 coins made up of dimes amd pennies whose total worth is \$ 11.25. How many of each coin must you have?

Exercise 1.4.25   Show that has no positive integer solutions.

David Joyner 2007-09-03