Some
properties of the
Euler Phi function:
-
phi(p)=p-1, for a prime number p
- More generally, phi(pn)=(pn-pn-1).
- if m and n have no common factor then
phi(mn)=phi(m)phi(n)
These last two allow us to give a
formula for the phi(
m) in terms of its decomposition as a product of prime powers (see
fundamental theorem of arithmetic).
phi(p1n1...ptnt) = (p1n1 - p1n1-1)...(ptnt - ptnt-1)
for distinct primes
pi and positive integers
ni.
a.k.a. Euler's Totient function
See: Proof of the properties of the Euler Phi function