|
The Euler Phi function, written φ(n) is the number of natural numbers coprime (gcd = 1) to n, and less than n. There are three facts about φ(n) which help us to calculate the value of the function for any given n, without the tedious process of working them all out: 1) If p is prime, then then φ(p) = p - 1 2) If pn is prime, then φ(pn) = pn - pn-1 3) If the gcd of a and b is 1 (ie they are coprime), then φ(ab) = φ(a)φ(b) |
|||