2.1 Topics in Number Theory 5

Definition 2.1.7 For n ≥1, let (n) denote the number of integers in the interval [1,n]

which are relatively prime to n. The function is called the Euler phi function.

Theorem 2.1.6 (properties of Euler phi function)

1. If p is a prime, then φ(p)=p - 1.

2. The Euler phi function is multiplicative. That is, if gcd(m, n) = 1, then

φ (mn)= φ (m) · φ (n).

k is the prime factorization of n, then

3. If p^e1. p^e2…p^ek

k (pk - 1)

φ (n)=p^(e1 -1) × p^(e2 -1) ×···×p^(ek -1)

= n (1 – 1/p1)(1-1/p2)…(1-1/pk).