Euler Totient Function

The Euler Totient Function is an arithmetic function defined as

i.e. the number of elements ${\displaystyle k\in \{1,...,n\}}$  that are coprime with ${\displaystyle n}$.

Theorem

    

Proof:- Note that each  ${\displaystyle k\in S=\{1,...,n\}}$  has a highest common factor ${\displaystyle h=gcd(k,n)}$ with ${\displaystyle n}$ and of course this is a factor of n.  So each ${\displaystyle k}$ belongs to a unique subset ${\displaystyle S_h}$, and these subsets have no overlapping elements.  In other words ${\displaystyle S=\{1,...,n\}}$ can be partitioned into a disjoint union
     ${\displaystyle S=\bigcup _h S_h}$
Counting the elements, we have
${\displaystyle \#S}$    =  ${\displaystyle \sum _{h|n}\#S_h}$
${\displaystyle n}$    =  ${\displaystyle \sum _{h|n}\#\{k:gcd(k,n)=h\}}$
        =  ${\displaystyle \sum _{h|n}\#\{k:gcd(k,\frac{n}{h})=1\}}$
        =  ${\displaystyle \sum _{h|n}\phi \left(\frac{n}{h}\right)}$
        =  ${\displaystyle \sum _{d|n}\phi \left(d\right)}$
[as ${\displaystyle h}$ runs through all the divisors of ${\displaystyle n}$, ${\displaystyle d=\frac{n}{h}}$ will also run through all the divisors of ${\displaystyle n}$]
(proven)
Here is another way to express the formula.

Example 1
For ${\displaystyle n=10}$, each of the numbers in ${\displaystyle \{1,2,...,10\}}$ belongs to exactly one of the subsets
     ${\displaystyle S_1 =\{1,3,7,9\}}$
     ${\displaystyle S_2 =\{2,4,6,8\}}$
     ${\displaystyle S_5 =\left\{5\right\}}$
     ${\displaystyle S_{10}=\left\{10\right\}}$
 Each subset ${\displaystyle S_h}$  is an equivalence class of the relation ~ (where ${\displaystyle a~b\iff }$${\displaystyle a}$ and ${\displaystyle b}$ share the same the highest common factor ${\displaystyle h}$ with 10).  Now observe
     ${\displaystyle S_1 =\{1,3,7,9\}}$,   ${\displaystyle ÷ 1}$, get ${\displaystyle \{1,3,7,9\} \subseteq \{1,...,10\}}$  ${\displaystyle \#=\phi \left(10\right)}$
     ${\displaystyle S_2 =\{2,4,6,8\}}$,   ${\displaystyle ÷ 2}$, get ${\displaystyle \{1,2,3,4\} \subseteq \{1,...,5\}}$   ${\displaystyle \#=\phi \left(5\right)}$
     ${\displaystyle S_5 =\left\{5\right\}}$            ,   ${\displaystyle ÷ 5}$, get ${\displaystyle \left\{1\right\} \subseteq \{1,...,2\}}$    ${\displaystyle \#=\phi \left(2\right)}$
     ${\displaystyle S_{10}=\left\{10\right\}}$        ,    ${\displaystyle ÷10}$, get ${\displaystyle \left\{1\right\} \subseteq \left\{1\right\}}$              ${\displaystyle \#=\phi \left(1\right)}$
Hence
     ${\displaystyle \#S_1+\#S_2+\#S_5+\#S_{10}}$
=   ${\displaystyle \phi \left(10\right)+\phi \left(5\right)+\phi \left(2\right)+\phi \left(1\right)}$
=   ${\displaystyle 4+4+1+1}$
=   10

Example 2
Try to work out the example for ${\displaystyle n=12}$, and check your work here.