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,

$$\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

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

(b) Let

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

(c) Let

$$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

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