Please Login to access more options.

Problem 64 ($\langle a^i \rangle = \langle a^j \rangle$ iff $\gcd(i,n)=\gcd(j,n)$)

Let $G$ be a group. Suppose that $a\in G$ has order $n>1$. Prove the following two facts:

  1. If $G$ is a cyclic group, then the order of $a$ divides the order of the group.
  2. We have $\langle a^i \rangle = \langle a^j \rangle$ if and only if $\gcd(i,n)=\gcd(j,n)$.

Click for a hint.

  1. If $G$ is cyclic, then pick a generator, say $b$. This means $G=\langle b\rangle$. Why does this mean $a=b^k$ for some $k$? Use this to show that $b$ has finite order, say $m$. Then use problem 63 with $b^k$, where $|b|=m$, rather than $a^k$ and $|a|=n$.
  2. Problem 63 will get you one direction, and problems 62 will get you the other.

The second fact proves the following three corollaries by letting $i=1$.

  • We have $\langle a \rangle = \langle a^j \rangle$ if and only if $\gcd(n,j)=1$.
  • A simple shift permutation $\phi_j$ on $n$ letters generates all simple shift permutations on $n$ letters if and only if $\gcd(n,j)=1$.
  • An integer $j\in \mathbb{Z}_n$ is a generator of $\mathbb{Z}_n$ if and only if $\gcd(n,j)=1$.

What does this have to do with the problem When Does An Integer Have A Modular Multiplicative Inverse? You should see a connection between this problem and elements of $U(n)$.

The following pages link to this page.