Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Which elements x^r in cyclic group Z_k have order k? (This will be a condition involving the two positive integers r and k.)

Example given by professor:

Consider the cyclic group of order k given by Z_k = {1, x, x^2, x^3, ... , x^(k-1)}, where x^k = 1 = x^0 and where one defines

(x^i) * (x^j) := x^t, where i+j = m*k + t

for t in {0, 1, 2, ... , k-1} and m is an integer not smaller than 0 ("nonnegative"). That is, "i+j is equal to t modulo k", t is the remainder when one divides i+j by k.

The order of the element x is k since k is the least positive integer such that x raised to the power is 1. Order of the identity element isn't defined as every power is the identity.

E.g., if k = 3, then (x^2) * (x^2) = x^1 = x, while (x^1) * (x^2) = x^3 = x^0 = 1. Hence, the powers of x^2 are the same as the powers of x but in a different order. Indeed, (x^2)^2 = (x^2) * (x^2) = x and (x^2)^3 = (x^2)^2 * (x^2) = x * (x^2) = x^3 = 1 so the order of x^2 is equal to 3 which is the same as the order of x.

share|improve this question
add comment

2 Answers

Hint: in a cyclic group like $\langle\mathbb{Z}_k, + \rangle$ of order $k$, if $\gcd(k, r) = 1$, then $|x^r| = k$, $1\leq r \leq k$. Written additively, this means that in this specific group, all elements $rx$ (e.g., here $x = 1$) will have order $k$ if and only if $\gcd(r, k) = 1$. If and only if $r$ and $k$ are relatively prime.

share|improve this answer
    
+1 I think it is conventionally accepted that for Abelian groups we used $rx$ instead of $x^r$. –  B. S. Feb 5 '13 at 2:44
add comment

If $\rm\,x\,$ has order $\rm\,\color{#C00}{ k}\,$ and $\rm\,r,k\,$ have a common factor $\rm\,d > 1,\,$ then $\rm\,x^r\,$ has order $\rm\, \le\color{#0A0}{k/d} < k\, $ since

$$\rm (x^r)^{\color{#0A0}{k/d}} = (x^k)^{r/d} = 1^{r/d} = 1$$

Conversely if $\rm\,r,k\,$ are coprime then $\rm\,x^r\,$ has order $\rm\,k\,$ since

$$\rm (x^r)^n = 1\iff \color{#C00}k\,|\,rn\iff k\,|\,n\ \ \ by\ Euclid's\ Lemma$$

Remark $\ $ Generally $\rm\,x^r\,$ has order $\rm\,k/gcd(r,k),\,$ by cancelling $\rm\,gcd(r,k)\,$ from above.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.