Math and science::Algebra::Aluffi

Euler's \( \phi \)

Euler's \( \phi \)-function

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

\[ \phi(m) = \left| \{ r \in \mathbb{N} : r \leq m, \gcd(r,m) = 1 \} \right| \]

A related theorem:

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

\[ \sum_{m > 0, m | n} \phi(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 \). \( \phi(m) \) is the number of such integers, and so \( \phi(m) \) is the number of generators of the subgroup \( C_{n/m} \). In this way, \( \sum_{m > 0, m | n} \phi(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 \( \phi \)

Euler's \( \phi \)-function

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

Proof

Example

\(C_{12}\): map from elements to subgroups.