##

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**.
**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.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.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.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