Euler's phi function

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

Definition 1.4.9   The number of integers $ 1\leq a\leq b$ which are relatively prime to $ b$ is denoted $ \phi(b)$, called the Euler $ \phi $-function or the Euler totient function.

Example 1.4.10 (1)   $ gcd(3,5)=1$, $ gcd(7,19)=1$, and more generally, any two distinct primes are always relatively prime.

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

$\displaystyle \phi (p)=p-1, $

where $ p$ is any prime number.

(3) We have the following table of values of $ \phi(n)$ for small $ n$:

$ n$ 1 2 3 4 5 6 7 8 9 10
$ \phi(n)$ 1 1 2 2 4 2 6 4 6 4

Corollary 1.4.11   Let $ a>0$ and $ b>0$ be integers. $ a$ is relatively prime to $ b$ if and only if there are integers $ x,y$ such that $ ax+by=1$.

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

(if) If $ d\vert a$ and $ d\vert b$ then $ d \vert( ax+by)$, so $ d\vert 1$. This forces $ d=\pm 1$, so $ gcd(a,b)=1$. $ \Box$

The fastest way to compute $ \phi(n)$ is to use the formula $ \phi(n)=\phi(a)\phi(b)$, assuming one can factor $ n=ab$ into relatively prime factors $ a>0$ and $ b>0$. The proof of this fact and more details on the Euler $ \phi $-function will be given later in §1.6.

Exercise 1.4.12   Find integers $ x$, $ y$, and $ d=gcd(a,b)$ for which $ ax+by=gcd(a,b)$, where

(a) $ a=155$ and $ b=15$,

(b) $ a=105$ and $ b=100$,

(c) $ a=15$ and $ b=51$.

Exercise 1.4.13 (a)   Let

$\displaystyle I=\{4m+10n\ \vert\ m,n\in \mathbb{Z}\}. $

(b) Let

$\displaystyle I=\{9m+10n\ \vert\ m,n\in \mathbb{Z}\}. $

(c) Let

$\displaystyle I=\{15m+51n\ \vert\ m,n\in \mathbb{Z}\}. $

Use Theorem 1.4.3 to find an $ a\in \mathbb{Z}$ such that $ I=a\mathbb{Z}$.

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 $ \phi(25)$, $ \phi(50)$, $ \phi(100)$.

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

$\displaystyle I=\{4m+6n\ \vert\ m,n\in \mathbb{Z}\} $

closest to (and including) 0.

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

(c) Use part (a) to find an $ m\in \mathbb{Z}$ such that $ I=m\mathbb{Z}$. (You know such an $ m$ exists by the above Lemma 1.4.2.)

Exercise 1.4.20 (a)   Let $ I=3\mathbb{Z}=\{3n\ \vert\ n\in \mathbb{Z}\}$.

(b) Let $ I=5\mathbb{Z}=\{5n\ \vert\ n\in \mathbb{Z}\}$.

Show that $ I$ is an ideal.

Exercise 1.4.21   Prove or disprove: For $ n>1$, $ n$ is a prime if and only if $ \phi(n)=n-1$.

Exercise 1.4.22   Show that $ 8x+20y=30$ has no integer solutions.

Exercise 1.4.23   Find all the integers $ x$ and $ y$ which satisfy both $ 2x+y=4$ and $ 3x+7y=5$.

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 $ 8x+20y=44$ has no positive integer solutions.


David Joyner 2007-09-03