####
**MATH-TRICK-8**

*This is trick no-10. A saying about one of my favourite mathematician is "Euler calculated without apparent effort,just as men breathe,as eagles sustain themselves in the air". Here is a beautiful trick:*

Here is the notions of Euler's phi-function and also its application to solve problems on abstract algebra from TIFR previous year paper.

**•EULER'S PHI FUNCTION:-**

The number of integers ≤ n and co-prime to n is called Euler's function for n & is denoted by ϕ(n).

__Ex.__

I. ϕ(1)=1 (since 1 is the only integer ≤1 and co-prime to 1)

II. ϕ(8)=4 (since 1,3,5,7 are the only four integers <8 and co-prime to 8)

III. ϕ(12)=4 (since co-prime integers less than 12 are 1,5,7,11).

__Properties:-__

I. ϕ(n) is a multiplicative function.

II. For n>2, ϕ(n) is an even integer.

Proof:- If (a,n)=1 then (n-a,n)=1

Thus integers co-prime to n occur in pairs of type a and n-a.

So, ϕ(n) is even.

__Note:__-

I. If p is prime,then ϕ(p)=p-1.

II. If a,b,c,d, . . . are positive integers prime to each other,then ϕ(abcd . . .)=ϕ(a)ϕ(b)ϕ(c)ϕ(d) . . .

III. If a,b,c, . . . .,p are distinct prime factor of n,then ϕ(n)=n(1- 1/a)(1- 1/b)(1- 1/c). . . . .(1- 1/p).

**Problem:- Calculate ϕ(1001).**

Sol:- 1001=13*7*11,where the numbers are relatively prime to each other.

So, ϕ(1001)=ϕ(13)ϕ(7)ϕ(11)

= 12.6.10=720.

(since 13,7,11 are all prime numbers)

**Application of Euler's function in abstract algebra:-**

It uses to determine the number of generators of a finite cyclic group.

__Result:- The total number of generators of a finite cyclic group of order n is ϕ(n).__

**Examples:-**

I. The number of generators of the cyclic group (S, . ) where S={1,i,-1,-i} is 2, since ϕ(4)=2.

II. The number of generators of the cyclic group of a prime order p is p-1 since ϕ(p)=p-1

**Problem:[TIFR-GS-2010] A cyclic group of order 60 has**

**A.12 B.15 C.16 D.20 generators.**

Sol:- (C) We need to find ϕ(60)

ϕ(60)=ϕ(3)ϕ(4)ϕ(5)=2.2.4=16,

Since 3,4,5 are relative primes.

And ϕ(4)=4(1 -1/2)=2

Since 3,5 are primes so ϕ(3)=2,ϕ(5)=4.