Euler's Totient Function
\[\tau (n)\]
is the number of distinct divisors of \[n\]
, including 1 and \[n\]
.Theorem
If
\[n=p_1^{k_1}p_2^{k_2}...p_r^{k_r}\]
then \[\tau (n)=(k_1+1)(k_2+1)...(k_r+1)\]
.Proof
Any divisor of
\[n\]
is of the form \[d=p_1^{s_1}p_2^{s_2}...p_r^{s_r}, \; s_r \le k_r \]
.There are
\[k_1+1\]
possible values of \[s_1\]
(\[s_1=0,1,2,...,k_1\]
), \[k_2+1\]
possible values of \[s_2\]
and so on, so \[(k_1+1)(k_2+1)...(k_r+1)\]
possible set of values of \[s_1, \; s_2,..., \; s_r\]
and each distinct choice gives rise to a distinct divisor because of the uniqueness prime decomposition. 
