Why need of totient function to find generators of cyclic group $C_n$?

123 Views Asked by At

Cyclic groups are defined where repeated application of the group operation is applied, to generate whole group, to generator element.

But, have confusion as have seen questions that ask about generators of group for a given value of $\mathbb{Z_{n=p}}, \mathbb{Z_{n= p^r}}$ here.

As $+\pmod n$ is operation for Cyclic Group $C_n$, so shouldn't all elements of $C_n$ be generators, irrespective of whether $n$ is prime or composite?

$ \begin{array}{c|ccccc} + \pmod 6 & 0 &1 & 2& 3 & 4 & 5\\ \hline 0 & 0 & 1 &2 & 3& 4 & 5\\ 1 & 1& 2 & 3& 4 & 5 & 0\\ 2 & 2 & 3 & 4 & 5 & 0 & 1 \\ 3 & 3 & 4& 5& 0& 2 &0\\ 4 & 4 & 5& 0& 1& 2&3 \\ 5 & 5 & 0& 1& 2& 3& 4\\ \end{array} $

The need for totient function should instead arise only in multiplicative table $<\langle \mathbb{Z}/p\mathbb{Z} \setminus\{0\}, *\rangle$, but that doesn't form a group even.

$ \begin{array}{c|ccccc} \times \pmod 6 &1 & 2& 3 & 4 & 5\\ \hline 1 & 1& 2 & 3& 4 & 5 \\ 2 & 2 & 4 & 0 & 2 & 4\\ 3 & 3 & 0& 3& 0& 3\\ 4 & 4 & 2& 0& 4& 2 \\ 5 & 5 & 4& 3& 2& 1\\ \end{array} $

Here, only elements ($1,5$) given by totient function are generators.

Edit. the way operations are applied is not in the sense of cyclic.

The correct approach is: $\begin{array}{c|ccccc} + \pmod 6 & a^0 & a^1 &a^2 & a^3& a^4 & a^5\\ \hline 0 & 0 &0 & 0& 0 & 0 & 0\\ 1 & 0& 1 & 2& 3 & 4 & 5\\ 2 & 0& 2 & 4 & 0 & 2& 4 \\ 3 & 0 & 3& 0& 3& 0&3\\ 4 & 0 & 4& 2& 0& 4&2 \\ 5 & 0 & 5& 4& 3& 2& 1\\ \end{array} $

$ \begin{array}{c|ccccc} \times \pmod 6 &a^1 & a^2& a^3 & a^4 & a^5\\ \hline 1 & 1& 1 & 1& 1 & 1 \\ 2 & 2 & 4 & 2 & 4 & 2\\ 3 & 3 & 3& 3& 3& 3\\ 4 & 4 & 4& 4& 4& 4 \\ 5 & 5 & 1& 5& 1& 5\\ \end{array}$

Have still one more doubt: is the first column of the additive group having entries $=0$ correctly?

1

There are 1 best solutions below

3
On BEST ANSWER

First, I am your downvoter. You keep biting off more than you can chew. It's quite a mess.

However, here's one more college try:

A basic fact about cyclic groups, which it would be great progress if you would learn to prove, is that $|g^k|=n/\gcd(n,k)$, where $n=|g|$.

This explains why Euler's totient function comes into play.