Show that the number of generators of a finite cyclic of order n is (n) where (n) is the Euler function

To demonstrate that the number of generators of a finite cyclic group of order \( n \) is given by \( \phi(n) \), where \( \phi \) is the Euler's totient function, we need to delve into some group theory concepts and properties of integers. Let's break this down step by step.

Understanding Cyclic Groups

A cyclic group is a group that can be generated by a single element. This means that every element in the group can be expressed as a power of this generator. For a finite cyclic group of order \( n \), we can denote it as \( G = \langle g \rangle \), where \( g \) is a generator of the group and \( |G| = n \).

Identifying Generators

In a cyclic group, an element \( g^k \) (where \( k \) is an integer) is a generator if and only if the order of \( g^k \) is equal to \( n \). The order of an element \( g^k \) is given by \( \frac{n}{\text{gcd}(n, k)} \). For \( g^k \) to be a generator, we require:

• \( \frac{n}{\text{gcd}(n, k)} = n \)

This simplifies to \( \text{gcd}(n, k) = 1 \). Thus, \( k \) must be coprime to \( n \) for \( g^k \) to generate the entire group.

Counting Suitable \( k \) Values

The integers \( k \) that satisfy \( 1 \leq k < n \) and \( \text{gcd}(n, k) = 1 \) are precisely those counted by the Euler's totient function \( \phi(n) \). The function \( \phi(n) \) counts the number of integers up to \( n \) that are coprime to \( n \).

Examples for Clarity

Let’s consider a couple of examples to solidify this concept:

Example 1: \( n = 6 \)

The integers less than 6 are 1, 2, 3, 4, and 5. We check their gcd with 6:

• gcd(6, 1) = 1
• gcd(6, 2) = 2
• gcd(6, 3) = 3
• gcd(6, 4) = 2
• gcd(6, 5) = 1

Only 1 and 5 are coprime to 6. Thus, \( \phi(6) = 2 \), indicating that there are 2 generators for the cyclic group of order 6.

Example 2: \( n = 7 \)

Since 7 is a prime number, all integers from 1 to 6 are coprime to 7. Therefore:

• gcd(7, 1) = 1
• gcd(7, 2) = 1
• gcd(7, 3) = 1
• gcd(7, 4) = 1
• gcd(7, 5) = 1
• gcd(7, 6) = 1

This gives us \( \phi(7) = 6 \), meaning there are 6 generators for the cyclic group of order 7.

Final Thoughts

In summary, the number of generators of a finite cyclic group of order \( n \) is indeed \( \phi(n) \). This relationship highlights the connection between group theory and number theory, showcasing how the structure of groups can be analyzed through the properties of integers. Understanding this concept is fundamental in both abstract algebra and its applications in various mathematical fields.