## 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 2008-04-20