5
$\begingroup$

Given the following Euler groups : $$\begin{align*} U_{12} &= \{1,5,7,11\}\\ U_{16} &= \{1,3,5,7,9,11,13,15\} \end{align*}$$

I want to prove that they are not cyclic. I used the following theorem :

A group of order $n$ is cyclic if and only if it has an element of order $n$.

Let's take for example $U_{12}$: (I will use the notation of $o(x)$ to denote the order of the element $x\in G$)
$$\begin{align*} o(5)&\colon 5^2=25 \to 25\bmod 12 = 1\to o(5)=2\\ o(7)&\colon 7^2= 49 \to 49\bmod 12 = 1 \to o(7)=2\\ o(11) &\colon 11^2 = 121 \to 121\bmod 12=1 \to o(11)=2 \end{align*} $$

Then by using the above theorem , this group is indeed not a cyclic group.

Question : do I really have to check each element in the group for its order ?

Regards

  • 1
    BTW, the structure of the [multiplicative group of integers modulo n](http://en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n) $U_n$ is will known. In particular, it is cyclic iff $n$ is 2, 4, any power of an odd prime or twice any power of an odd prime.2012-03-09
  • 0
    Please learn some basic $\LaTeX$ instead of waiting for others to pretty up your posts for you. Thank you.2012-03-09
  • 1
    Comment: Stop using $\to$ to mean "and since" or some other connectives. The arrow has specific meanings in mathematics; students who use $\to$ and $=$ as general purpose connectives to mean something like "and then I did some thinking and this is what I came up with" drive professors crazy.2012-03-09
  • 1
    @Arturo, I don't think driving professors crazy is the real problem - for most of us, crazy is within walking distance, anyway - I think the real problem is the student who writes that way is pretty much guaranteed to get things wrong.2012-03-10

4 Answers 4

0

What of if your set is infinite? I think the best idea is to find the general form of the elements in the set (if possible) and pick arbitarary element, check your assertion and then generalised. But in your case, since the elements are finite, you have to check it for all the elements in the set.

5

Some shortcuts are available. For example, when testing $3$ in $U_{16}$, you find its powers are $3,9,11,1$, so you don't have to test $9$ or $11$. Do you see why?

  • 0
    I didn't get your meaning .What do you mean by "its powers" ? 3^3 = 27 --> 27 modulo 16= 11 .... so I generated using 3 , the element 11 . What does it mean ?2012-03-09
  • 0
    You're trying to decide whether the order of $3$ is $8$. So you look at $3$, then at $3\times3=9$, then at $3\times3\times3=3\times9=27=11$, then at $3\times3\times3\times3=3\times11=33=1$. Those are the powers of $3$, the numbers $3^r$, $r=1,2,3,\dots$. Using $3$, you generate $3$, $9$, $11$, and $1$.2012-03-09
  • 0
    Okay , so now we know that the order of |3|=4 . Why does it help me ? now I won't need to check the generated elements using 3 ?2012-03-09
  • 0
    "Why does it help me ?" This is an exercise for the reader -- use knowledge about the order of $3$ in order to deduce something about the order of $3^2$....2012-03-09
  • 0
    You should see if you can prove that if $g$ doesn't generate $G$ and $h$ is in the subgroup generated by $g$ then $h$ doesn't generate $G$ either.2012-03-10
4

As I mentioned yesterday in reply to a question of yours: a cyclic group has at most one element of order $2$.

You accepted that answer. Didn't you read it before accepting it?

In your first two lines, you've shown that $5$ and $7$ both have order $2$ in $U_{12}$. Therefore, the group cannot be cyclic.

Similarly, since $9^2\equiv 1\pmod{16}$ and $15^2\equiv 1\pmod{16}$, $U_{16}$ has at least two distinct elements of order $2$, and therefore cannot be cyclic.

In general, a cyclic group of order $n$ has exactly $\phi(d)$ elements of order $d$ for each divisor $d$ of $n$.

3

Well really the "theorem" is the definition of cyclic group...it is a group generated by one element.

Now if I give you a group and you check that all but one element isn't a generator, how do you know that the one you didn't check isn't a generator?

So yes, you must check ALL elements.

  • 1
    ... or you can use interesting theorems. For example, there's an easy upper bound on the number of elements of order 2....2012-03-09