Euler Function
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 = 22 • 3, i.e. Φ (12) = 12 • (1 - 1/2) • (1 - 1/3) = 12 • 2 / (2 • 3) = 4.
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 a4 = 1 (mod 12).
3. Φ (m1m2) = Φ (m1) Φ (m2) for co prime m1 and m2
Reference
1. http://www.cat4mba.com/node/3359#comment-1355