Euler’s phi function

Euler’s phi function \phi(), or totient, counts how many positive integers lower than m have no common divisor with m.

The \phi function was first studied by Euler, though it was Gauss who named it \phi and established that, for any positive integer n,

(1)   \begin{equation*} \boxed{\sum_{d\mid n} \phi(d) = n} \end{equation*}

where the summation is over all positive divisors d of n.

\phi(mn) = \phi(m)\phi(n) when gcd(m,n) = 1. (Euler 1761)

\phi(n) is also naturally the number of proper fractions in lowest terms with denominator n. e.g. for n=6, there are (1/6, 5/6) and \phi(6)=2.

Leave a Reply

Your email address will not be published. Required fields are marked *