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)$.

Solution

Let $G$ be a group. Suppose that $a\in G$ has order $n>1$. We will 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 $\text{gcd}(i,n)=\text{gcd}(j,n)$.

1. Let $G$ be a cyclic group generated by the element $b$ and suppose that $a\in G$ has order $n>1$. This means $G=\langle b\rangle$. We also know that $|b|=|\langle b\rangle|$. From these two facts we know that if $b$ has an order then $|G|=|\langle b\rangle|=|b|$. Therefore, to show that $G$ has an order we must show that $b$ has an order.

Recall that $a\in G$ and has finite order $n$. From the definition of $\langle b\rangle$ we can write $a=b^k$ for some $k\in\mathbb{Z}$. In addition, from the definition of order we know that $a^n=e$. Thus, we know that $a^n=(b^k)^n=e$. Hence, the fact that $(b^k)^n=e$ means that we can conclude that $b$ has some finite order that is less than or equal to $kn$. Thus, $b$ has a finite order denoted $|b|$. Since $|b|=|G|$, then we can conclude that the group $G$ has a finite order $|b|$.

We will now prove that the order of $a$ divides the order of the cyclic group $G$. Recall that $a=b^k$ and problem 63. This means $|a|=|b^k|=\frac{|b|}{\text{gcd}(k,|b|)}$. Thus, we know that $|b|=|a|\text{gcd}(k,|b|)$ by integer multiplication of the $\text{gcd}(k,|b|)$ on both sides of the equation. This means that $|b|$ is a multiple of $|a|$. In other words, $|a|$ divides $|b|$. Since $|b|=|G|$, we know that $|a|$ divides $|G|$. $\blacklozenge$

2. We will prove that $\langle a^i\rangle =\langle a^j\rangle$ if and only if $\text{gcd}(i,n)=\text{gcd}(j,n)$.
Let $G$ be a group and suppose that $a∈G$ has order $n>1$. We will first prove that if $\text{gcd}(i,n)=\text{gcd}(j,n)$, then $\langle a^i\rangle =\langle a^j\rangle$.

Suppose $\text{gcd}(i,n)=\text{gcd}(j,n)$. Recall problem 62. This means $\langle a^i\rangle =\langle a^{\text{gcd}(i,n)}\rangle$. Similarly, $\langle a^j\rangle =\langle a^{\text{gcd}(j,n)}\rangle$. However, since $\text{gcd}(i,n)=\text{gcd}(j,n)$ it is clear that $\langle a^i\rangle =\langle a^j\rangle$.

We will now prove that if $\langle a^i\rangle =\langle a^j\rangle$, then $\text{gcd}(i,n)=\text{gcd}(j,n)$.

Supposed $\langle a^i\rangle =\langle a^j\rangle$. We know that $|\langle a^i\rangle |=|\langle a^j\rangle|$ which implies $|a^i|=|a^j|$. By recalling $|a|=n$ and problem 63 we know $\frac{n}{\text{gcd}(i,n)}=\frac{n}{\text{gcd}(j,n)}$.
Now, by cancellation laws of groups $\frac{1}{\text{gcd}(i,n)}=\frac{1}{\text{gcd}(j,n)}$. Then, by multiplication of integers, $\text{gcd}(i,n)=\text{gcd}(j,n)$.

Thus, $\langle a^i\rangle =\langle a^j\rangle$ if and only if $\text{gcd}(i,n)=\text{gcd}(j,n)$.$\blacklozenge$

Tags

Change these as needed.

  • When you are ready to submit this written work for grading, add the phrase [[!Submit]] to your page. This will tell me that you have completed the page (it's past rough draft form, and you believe it is in final draft form). Don't type [[!Submit]] on a rough draft.
  • If I put [[!NeedsWork]] on your page, then your job is to review what I've written, address any comments made, and then delete all the comments I made. When you have finished reviewing your work, leave [[!NeedsWork]] on your page and type [[!Submit]]. (Both tags will show up). This tells me you have addressed the comments.
  • I'll mark your work with [[!Complete]] after you have made appropriate revisions.