## Pages

### MATH TRICK-EULER'S PHI FUNCTION

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