BIGtheme.net http://bigtheme.net/ecommerce/opencart OpenCart Templates
Saturday , July 22 2017
Home / Elementary Number Theory / Euler’s Phi function

# Euler’s Phi function

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) = d1 > 1. Then d1 must have a prime divisor p. Because d1 | 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, d1 = 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)

## Application of Euclidian’s algorithm in Diophantine equation

Problem-1: Which of the following Diophantine equations cannot be solved –   a) 6x + ...