Eulers Totient Function

Set of Coprime Integers

Suppose that

n \in ℕ_{1}

then we define

cop (n) : = {k \in [1, \dots, n] : \gcd (k, n) = 1}

Euler's Totient Function

We define it as

ϕ : ℕ_{1} \to ℂ

ϕ (n) : = | cop (n) |

GCD Set

We define

G (d, n) : ℕ_{𝟙} \times ℕ_{1} \to ℕ_{1}

G (d, n) : = {k \in [1, \dots, n] : \gcd (k, n) = d}

Bijection between Cops and G's

Let

d, n \in ℕ_{1}

such that

d | n

| C_{d} | = | G (\frac{n}{d}, n) |

The GCD Sets form a Partition

The collection

{G (i, n) : i \in [1, \dots n]}

is a partition of

[1, \dots, n]

Euler's

For any

n \in ℕ_{1}

and

a \in cop (n)

we have

a^{ϕ} (n) \equiv 1 (\mod n)

\begin{matrix} * & ε & 1 & μ & ι \\ ε & ε & 1 & μ & ι \\ 1 & τ & ε & σ \\ μ & ? & ? \\ ι & ι τ \end{matrix}

Sum over Coprimes Totient Identity

Let

n \in ℕ_{3}

then

\sum_{k \in cop (n)} k = \frac{n ϕ (n)}{2}

Sum over Divisors of the Totient function is the Identity

For any

n \in ℕ_{1}

we have

ϕ * 1 = ι

, equivalently that is:

\sum_{d | n} ϕ (d) = n