Euler Totient Function

The Euler Totient Function is an arithmetic function defined as

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

Theorem

    

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

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

Example 2
Try to work out the example for `n=12`, and check your work here.