**Euler’s Phi function**: The number of positive integers less than or equal to a positive n and relatively prime to n is denoted by Φ(n). Φ(n) is called the Euler phi function.

# Theorem: If p is a prime then Φ(p) = p – 1

Proof: If p is a prime, then each of p – 1 positive integers less than p and relatively prime to p. But p is not relatively prime itself.

Hence Φ(p) = p – 1. (Proved)

**Lemma: Given integers a, b, c, gcd(a, bc) = 1 if and only if gcd(a, b) =1 and gcd(a, c) = 1.**

**Proof**: First suppose that gcd(a, bc) = 1 and put d = gcd(a, b). Then d|aand d|b, whence d|a and d|bc. This implies that gcd(a, bc) ≥ d, which forces d = 1. Similar reasoning gives rise to the statement gcd(a, c) = 1.

For the other direction, take gcd(a, b) = 1 = gcd(a, c) and suppose that gcd(a, bc) = d_{1} > 1. Then d_{1} must have a prime divisor p. Because d_{1} | bc, it follows that p | bc; in consequence , p|b or p|c then we have gcd(a, b) ≥ p, a contradiction. In the same way , the condition p|c leads to the equally false conclusion that gcd(a, c) ≥p. Thus, d_{1} = 1and the lemma is proved.

### Theorem: Euler’s phi(Φ) function is multiplicative.

Or, if (m, n) = 1, m > 1, n > 1 then Φ(mn) = Φ(m) Φ(n)

Proof: Let S= {k, k + a,…,k + (m – 1 )a} be a set of positive integers which are the m terms of an A. P series whose common difference is a and (a, m) = 1. Then we know that there are exactly Φ(m) integers prime to m in S.

Now Φ(mn) = number of integers less than mn and prime to it.

= number of integers less than mn which are relatively prime to both m and n.

To determine Φ(mn) we arrange the integers 1, 2, …mn in m rows and n columns as follows:

1 2 … k … n

n + 1 n + 2 … n + k … n + n

2n + 1 2n + 2 … 2 n + k … 2 n + n

… … … … … …

(m – 1 )n + 1 (m – 1 )n + 2 … (m – 1 ) n + k … (m – 1 ) n + n

Let us take the k-th column. The integers in this column are

k, n + k, 2n + k, … , (m – 1 ) + k …………………. (1)

There are m integers they from an A. P series whose common difference is n and (m, n) = 1.

∴ There are exactly Φ(m) integers prime to m.

Thus , each column contains exactly Φ(m) integers prime to m. Moreover, each term of (1) is prime to n if and only if (k, n) = 1. But we know that (k, n) = 1, for Φ(n) values of k.

∴ There are exactly Φ(n) columns in which every integer is prime to n and no integers in other columns is to prime to n.

Hence, there are in all Φ(m) Φ(n) integers less than mn and prime to both m and n.

Thus, Φ(mn) = Φ(m) Φ(n). (Proved)