Posts tagged ‘Cyclic group’

09/01/2017

Proof: any element of a group of prime order generates the group

Let G be a group of prime order |G|=p. It will be shown that for any a\in G with a\ne e it holds that \langle a\rangle=G, where \langle a\rangle is the set generated by a and e is the identity element of G.

Since the order of group G is |G|=p<\infty, the order \mbox{ord}(a) of element a is also finite, i.e. \mbox{ord}(a)=n<\infty for some positive integer n.

Note that the set \langle a\rangle=\left\{a^0,a^1,\ldots,a^{n-1}\right\} generated by a is a subgroup of G, since \langle a\rangle is closed with respect to multiplication and with respect to inverses. Indeed, for any a^i,a^j\in\langle a\rangle, the division algorithm of integers ensures that there exist integers q,r with 0\le r <n such that a^i a^j = a^{i+j}=a^{nq+r}=(a^n)^q a^r=e a^r=a^r\in \langle a \rangle. Moreover, the inverse of any a^i\in \langle a \rangle is (a^i)^{-1}=a^{n-i}\in \langle a \rangle.

The order |\langle a \rangle| of the cyclic subgroup\langle a \rangle of G is equal to the order of generator a, that is |\langle a \rangle|=\mbox{ord}(a)=n.

By Lagrange’s theorem, n is a factor of p. Since p is a prime, n=1 or n=p. It follows from a\ne e that n\ne 1, so n=p, which means that |\langle a \rangle|=|G|.

\langle a \rangle\subseteq G and |\langle a \rangle|=|G|\Rightarrow\langle a \rangle=G.

07/01/2017

Clarification on the proof of isomorphism of finite cyclic groups

In order to show that any two cyclic groups of finite order n are isomorphic to each other, it suffices to show that every cyclic group \langle a\rangle=\left\{a^0,a^1,a^2,\ldots,a^{n-1}\right\} of finite order n is isomorphic to the group \mathbb{Z}_n of integers modulo n with the operation of addition modulo n, where \mathbb{Z}_n=\left\{0,1,2,\ldots,n-1\right\}.

Towards this end, it can be shown that the function f:\mathbb{Z}_n\rightarrow\langle a\rangle defined as f(i)=a^i is a group isomorphism. Recalling the definition of group isomorphism, it suffices to show that f is a bijective homomorphism. It is straightforward to check that f is a bijective function. The fact that f is a homomorphism is proven also easily using laws of exponents for groups, as follows: f(i+j)=a^{i+j}=a^i a^j=f(i)f(j).

Proving the homomorphic property of f as above works well if f is taken to be f:\mathbb{Z}\rightarrow\langle a\rangle,~f(i)=a^i, that is from the additive group of integers to the cyclic group \langle a\rangle=\left\{\ldots,a^{-2},a^{-1},a^0,a^1,a^2,\ldots\right\} of infinite order generated by a. However, in the case of f:\mathbb{Z}_n\rightarrow\langle a\rangle with \langle a\rangle=\left\{a^0,a^1,a^2,\ldots,a^{n-1}\right\}, there is a slight oversight; the addition implied by f(i+j) is addition modulo n.

Let’s denote the addition modulo n by \oplus. So, now the proof of homomorphic property takes the form f(i\oplus j)=a^{i\oplus j}=a^i a^j=f(i)f(j). The identitya^{i+j}=a^i a^j is not the same asa^{i\oplus j}=a^i a^j; the former is one of the common exponent laws for groups, while the latter is not.

What needs to be shown is that the exponents of addition and of addition modulo n coincide, i.e. a^{i+j}=a^{i\oplus j}. The proof of this identity is simple, yet it is useful to be aware of such potential oversight.

According to the division algorithm for integers, there exist unique integers q and r such that i+j = nq+r and 0\le r < n. Thus, a^{i+j}=a^{nq+r}=(a^n)^q a^r. Since the cyclic group \langle a\rangle is of order n, it holds that a^n=e, where e is the identity element of \langle a\rangle. So, a^{i+j}=a^r.

Notice that r coincides with the result of the addition modulo n, that is r=i\oplus j. It follows that a^{i+j}=a^{i\oplus j}, which completes the proof.