Math and science::Algebra::Aluffi

Euler's $ϕ$

Euler's $ϕ$ -function

Euler's $ϕ$ -function maps any positive integer $m$ to the number of positive integers $r \leq m$ that are relatively prime to $m$ . In other words:

ϕ (m) = | {r \in N : r \leq m, gcd (r, m) = 1} |

A related theorem:

Theorem. N = sum of relative primes of divisors of N.

\sum_{m > 0, m | n} ϕ (m) = n

Proof is on the reverse side.

Proof

Proof. We will count generators in two ways.

Firstly, every element in the cyclic group $C_{n}$ is a generator of 1 subgroup of $C_{n}$ . There are no other subgroups, so this is a surjective map into the set of subgroups of $C_{n}$ .

Going in reverse, we will do a double loop, looping first over all subgroups, and then over the generators of each subgroup. Subgroups of $C_{n}$ are one-to-one with divisors of $n$ . Let $m$ be one such divisor. A generator of the subgroup $C_{n / m}$ is an integer that is relatively prime to $m$ . $ϕ (m)$ is the number of such integers, and so $ϕ (m)$ is the number of generators of the subgroup $C_{n / m}$ . In this way, $\sum_{m > 0, m | n} ϕ (m)$ is the sum of generators for all subgroups of $C_{n}$ .

Thus, the number of elements $n$ and the sum of generators of all subgroups of $C_{n}$ are the same.

Euler's $ϕ$

Euler's $ϕ$ -function

Theorem. N = sum of relative primes of divisors of N.

Proof

Example

$C_{12}$ : map from elements to subgroups.

Euler's ϕ

Euler's ϕ-function

Theorem. N = sum of relative primes of divisors of N.

Proof

Example

C12: map from elements to subgroups.

Euler's $ϕ$

Euler's $ϕ$ -function

$C_{12}$ : map from elements to subgroups.