Order of an element in U(Z_n)

[Absane]

Let's say we have the group $$U(\mathbb{Z}_{n}) = \{x : gcd(x, n) = 1 \}$$ under standard multiplication (if you doubt it's a group, go ahead and check).

My question is, say I want to find all $$x \in U(\mathbb{Z}_{n})$$ with order k and k divides the order of the group. Is there a way to find them without trial and error? Is there some rule I am missing?

 

[Absane]

I assume it all comes down to this:

Find $$x$$ such that $$x^{k} \equiv 1 mod \phi (n) $$ where $$\phi (n)$$ is the order of the group and checking which solution's don't also satisfy the same condition for a smaller power.

Edit: but that's hard to do.

 

[Absane]

Bump

 

[Absane]

bump

 

[Human001]

I think you want to find all x such that given a k where $$k|\phi(n)$$
and

$$x^{k}\cong 1 mod n$$
For this you want to look at the modulo multiplication group http://mathworld.wolfram.com/ModuloMultiplicationGroup.html
Clearly all groups U are abelian since normal multiplication is abelian and so are the direct products of cyclic groups.
The answer to your question depends on how many direct products U is made from.If it has just one, for example n is a prime, then there is only one $$x\in U$$ of order k.
But given more direct products this is not an easy problem.

 

[Human001]

However, If its possible to work out the structure of U(Z_n) for general n, and you know n is the product of cyclic groups, you can find all x such that x^k is cong....

For example. If U is isomorphic to $$C_{2}\times C_{2}\times C_{5}$$, then U has odrer 20 and lets put k=10. Now the element (1,0,1) has order 10 ((1,0,1)^2=(0,0,2)... and (1,0,1)^9=(0,0,4)) and (0,1,1)has order 10. Only. There are only two elements of order 10 in U.

What you need is a general method of finding the direct product factors of U. I dont know how to do that, but Im sure its possible.

 

[TheCareTaker]

Umm Say what
what does that equal?

 

[Human001]

What does what equal?
Im saying (in my own horribly unintelligable way) that we need to find the structure of U(Z_n) to answer Absanes problem.
I dont know how to work that out for general n. If anyone does it Id be very happy to see because I spent all last night trying to work out this with absolutely zero results.

 

[Human001]

As an example consider Z_20.
U(Z_20) is isomorphic to $$C_{2}\times C_{4}$$. We can write elements in the form (a,b) where $$a\in C_{2},b\in C_{4}$$.
Consider all elements of U of order 4.
We have (0,1) and (1,3). Both have order 4.