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 = 2² • 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 a⁴ = 1 (mod 12). 3. Φ (m1m2) = Φ (m1) Φ (m2) for co prime m1 and m2 Reference 1. http://www.cat4mba.com/node/3359#comment-1355