Order of element and order of cyclic group coincide

In summary, the conversation discusses a proof that if an element x in a group G has a certain order n, then the set of all powers of x has the same cardinality as the set of positive integers less than n. This is proven using the Euclidean algorithm and properties of modular arithmetic.
  • #1
Mr Davis 97
1,462
44

Homework Statement


Let ##G## be a group and ##x \in G## any element. Prove that if ##|x| = n##, then ##|x| = |\{x^k : k \in \mathbb{Z} \}|##.

Homework Equations

The Attempt at a Solution


Let ##H = \{x^k : k \in \mathbb{Z} \}##. I claim that ##H = \{1,x,x^2, \dots , x^{n-1} \}##. First, we show that these sets are equal. Let ##m \in \mathbb{Z}##. By the Euclidean algorithm, ##m = nq + r##, where ##r \in [1, n)##. Then ##x^m = x^{nq+r} = (x^n)^qx^r = x^r \in \{1,x,x^2, \dots , x^{n-1} \}##. The reverse containment is obvious. Now, we show that ##H## has ##n## distinct elements. Let ##i,j \in [1,n)## and suppose that ##x^i = x^j##. Then ##x^{i-j}=1##. So ##n ~ | ~ i-j##, which implies that ##i \equiv j ~ (\bmod n)##. But since ##1 \le i,j < n##, ##i = j##. Hence, all of the elements of ##H## are distinct and ##|x| = |H|##
 
Physics news on Phys.org
  • #2
Mr Davis 97 said:

Homework Statement


Let ##G## be a group and ##x \in G## any element. Prove that if ##|x| = n##, then ##|x| = |\{x^k : k \in \mathbb{Z} \}|##.

Homework Equations

The Attempt at a Solution


Let ##H = \{x^k : k \in \mathbb{Z} \}##. I claim that ##H = \{1,x,x^2, \dots , x^{n-1} \}##. First, we show that these sets are equal. Let ##m \in \mathbb{Z}##. By the Euclidean algorithm, ##m = nq + r##, where ##r \in [1, n)##. Then ##x^m = x^{nq+r} = (x^n)^qx^r = x^r \in \{1,x,x^2, \dots , x^{n-1} \}##. The reverse containment is obvious. Now, we show that ##H## has ##n## distinct elements. Let ##i,j \in [1,n)## and suppose that ##x^i = x^j##. Then ##x^{i-j}=1##. So ##n ~ | ~ i-j##, which implies that ##i \equiv j ~ (\bmod n)##. But since ##1 \le i,j < n##, ##i = j##. Hence, all of the elements of ##H## are distinct and ##|x| = |H|##
Looks good. Only one minor mistake: The lower bound for the remainders is ##0##, not ##1##, so ##r,i,j \in [0,n)## and ##0\leq i,j <n ## which doesn't harm the proof, as ##x^0=1\,.##
 
  • Like
Likes Mr Davis 97

Related to Order of element and order of cyclic group coincide

1. What is the meaning of "order of element and order of cyclic group coincide"?

"Order of element and order of cyclic group coincide" refers to a property of a cyclic group, where the order (or number of elements) of the group is equal to the order of its generating element. This means that the generating element can be used to create all other elements in the group.

2. How can you determine the order of a cyclic group?

The order of a cyclic group can be determined by finding the smallest positive integer n such that the group's generating element raised to the power of n equals the identity element of the group. This n will also be the number of elements in the group.

3. Can a non-cyclic group have the same order as its generating element?

No, a non-cyclic group cannot have the same order as its generating element. This is because the generating element of a non-cyclic group cannot create all other elements in the group, so the order of the group will always be greater than the order of the generating element.

4. How can the order of a cyclic group be used in cryptography?

The order of a cyclic group is often used in cryptography systems, specifically in the Diffie-Hellman key exchange algorithm. This algorithm relies on the difficulty of calculating discrete logarithms in cyclic groups, which is related to the order of the group.

5. Are all cyclic groups also abelian?

Yes, all cyclic groups are also abelian, meaning that their group operation is commutative. This is because cyclic groups are generated by a single element, so the order in which operations are performed does not affect the outcome.

Similar threads

  • Calculus and Beyond Homework Help
Replies
3
Views
555
  • Calculus and Beyond Homework Help
Replies
1
Views
488
  • Calculus and Beyond Homework Help
Replies
8
Views
191
  • Calculus and Beyond Homework Help
Replies
9
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
378
  • Calculus and Beyond Homework Help
Replies
3
Views
844
  • Calculus and Beyond Homework Help
Replies
1
Views
607
  • Calculus and Beyond Homework Help
Replies
1
Views
567
  • Calculus and Beyond Homework Help
Replies
1
Views
548
  • Calculus and Beyond Homework Help
Replies
2
Views
963
Back
Top