CAT4MBA

In number theory, the totient ( also called phi) Φ (n) of a positive integer n is defined as the number of positive integers less than or equal to n that are co prime to n.
For example, Φ(9) = 6 since the six numbers 1, 2, 4, 5, 7 and 8 are co prime to 9.

A few first values: Φ (1)=1, Φ (2)=1, Φ (3)=2, Φ (4)=2, Φ (5)=4, Φ (6)=2, Φ (7)=6, Φ (8)=4, Φ (9)=6, Φ (10)=4, Φ (11)=10, Φ (12)=4, Φ (13)=12, etc., do not appear to follow any law.

But there is a formula discovered by Euler to which helps in calculating these numbers. According to Euler

Example: 12 = 2² • 3, i.e. Φ (12) = 12 • (1 - 1/2) • (1 - 1/3) = 12 • 2 / (2 • 3) = 4.

Reminder Theorem

If Φ(n) is the eulers numbr of integer n, the reminder obtained when m^Φ(n) is divided by n is 1.

Properties
1. The sum over the Euler function values Φ (d) of all divisors d of an integer number n exactly gives n. E.g. for n=12: Φ (1) + Φ (2) + Φ (3) + Φ (4) + Φ (6) + Φ (12) = 1 + 1 + 2 + 2 + 2 + 4 = 12

2. if GCD(a,n) = 1, then a^Φ(n) = 1 (mod n). For example, Φ (12)=4, so if gcd(a,12) = 1, then a⁴ = 1 (mod 12).

3. Φ (m1m2) = Φ (m1) Φ (m2) for co prime m1 and m2 Reference 1. http://www.cat4mba.com/node/3359#comment-1355

4. From Nishit's comment @ http://www.cat4mba.com/node/3359?page=4

Euler's Function for number N

e(N) = N(1 - 1/p₁)(1 - 1/p₂)(1 - 1/p₃) . . . . . .
Where p₁, p₂, p₃, . . . , p_n are prime factors of N.

For example if N=60 = 2 x 2 x 3 x 5

then e(N) = 60 (1-1/2) (1-1/3) (1-1/5) = 60 x 1/2 x 2/3 x 4/5 = 16

I think Its wrong to calcualte like 60(1-1/2)(1-1/2)(1-1/3) (1-1/5)

Another way of finding it 

60 = 2² x 3¹ x 5¹

So e(60) = 2¹  x(2-1) x  3⁰ x (3-1) x 5⁰ x (5-1) = 16

 i.e if N = X^a   Y^b  Z^c

then  e(N) = X^a-1(X-1)  Y^b-1(Y-1)  Z^c-1(Z-1)