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:
A related theorem:
Theorem. N = sum of relative primes of divisors of 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. Its generators are \( g^{k(n/m)} \) with \( \gcd(k,m)=1 \). \( \phi(m) \) is the number of such integers \( k \), 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.
Intuition: consider \( C_6 \). \( \{ e, 2, 4\}\) is a subgroup with 3 elements. Both 2 and 4 are generators for this subgroup. This corresponds to 1 and 2 being coprime to 3. This 3 here is counting the elements of the subgroup. 3 is a factor of 3, and \(g^2g^2g^2 =0\) and this element (additive identity) doesn’t generate the subgroup.
Example
\(C_{12}\): map from elements to subgroups.
