Results are out! Find what you need...fast. Get quick advice or join the chat
Hey there Sign in to join this conversationNew here? Join for free

Can anybody check my proof?

Announcements Posted on
Got a question about Student Finance? Ask the experts this week on TSR! 14-09-2014
    • Thread Starter
    • 0 followers
    Offline

    ReputationRep:
    If G has no proper subgroups, prove that G is cyclic of order p, where p is a prime number.

    Assume that G has no proper subgroups, i.e., if H is a subgroup of G, then H={e} or H=G.

    If G={e}, then {e} is clearly cyclic. (e)={e}.
    If G=/= {e}, then ther eis an a in G with a =/= e. Then (a) is a subgroup of G, (a) =/= {e}. Then our assumption that G has no proper subgroups implies that (a)=G, so G is cyclic. Actually, the cyclic subgroup of any element of G is equal to G (since there can be no proper subgroups).

    Then (a) is a subgroup of G, where (a)=/={e}. Then our assumption that G has no proper subgroups, implies that (a)=G, so G is cyclic.

    For contradiction, assume that such a group is of nonprime order. So G={e,a,a^2,...,a^(n-1)} where n=qb with q,b in Z, and where q and b are not equal to 1 or n (since n is not prime, this must be possible). Since b < qb-1, a^b must be an element of G. According to the assumption, (a^b)=G.

    (a^b) = {e, a, a^2, ... , a^(n-1)}. So there must be an element k in G such that kb= qb-1 (mod n) (this is of course a congruence sign, not an equal sign).
    So n divides qb-1-kb. So there is an integer c such that

    qb-q-kb= nc
    qb-1-kb=(qb)c
    b(q-k)-1=c(qb)
    We know that b(q-k)-1 < b(q-k) < qb < c(qb). So b(q-k)-1 < c(qb).

    So the equality sign is not true, and this is a contradiciton.

    Is my proof correct? If not, can you please tell me why?

    Thanks in advance
    • 0 followers
    Offline

    ReputationRep:
    Hi, it gets a bit complicated towards the end and I'd have just shown that a^b has order q by construction.

    In fact, I kind of don't understand it, could you explain further?
    • 0 followers
    Online

    ReputationRep:
    I don't like the bit about justifying that the order of G is prime - you can just say something like -

    Let g be a generator of G. Suppose that |G| is not prime; so |G| = ab for some a,b both at least 2. Then <g^a> is a cyclic subgroup of G with order b.

    (If you think it's too much to just write down that g^a has order b so <g^a> is cyclic of order b, it's enough to show the weaker statement that g^a has order more than one and at most b, so the order of <g^a> is strictly between 2 and b)
    • Thread Starter
    • 0 followers
    Offline

    ReputationRep:
    (Original post by Jodin)
    Hi, it gets a bit complicated towards the end and I'd have just shown that a^b has order q by construction.

    In fact, I kind of don't understand it, could you explain further?
    This is what I was trying to say:

    At first, I show that H is either equal to {e} or to to G.

    When H=G, all the cyclic subgroups of the elements of G equal to G (because there are no proper subgroups of G). The question says that we have to show that such a group has order p, where p is prime.

    I tried to use contradiction. My proof tried to show that such a group (where H=G) can exist without have order p (which is a contradiction of course).

    So G = {e, a, a^2, ... ,a^(n-1)}. Since n is nonprime, there exist two integers q and b (where q=/=1 or n and b=/=1 or n), such that n=qb.

    Now I have to prove that all cyclic groups in G are equal to G (since G has no proper subgroups). I chose to look at a^b (we know that a^b is in G, since b < n-1 = qb-1) and show that it cannot equal to G, since there is no integer k, such that kb=qb-1 (mod n).

    This is how I tried to show it:

    kb=qb-1 (mod n) ==> n divides qb-1-kb ==> there exists an integer "c", such that nc=qb-1-kb. So...

    nc=qb-1-kb
    (qb)c= b(q-k)-1

    We know that b(q-k) - 1 < b(q-k) < qb < (qb)c. So b(q-k)-1 < (qb)c. In other words, this is an inequality. So my assumption that there exists a "c" such that nc=qb-1-kb is wrong. Which means that there is no k such that kb=qb-1 (mod n). Which, in turn, means that the cyclic subgroup of a^b does not contain the last element of G, which is a^(n-1). So this must be a proper subgroup...but the type of group that is described in the question says there are no proper subgroups. This is a contradiction...

    Do you think my proof is correct? If not, can you tell me where I'm going wrong? Thanks.
    • 0 followers
    Online

    ReputationRep:
    (Original post by Artus)
    This is what I was trying to say:

    At first, I show that H is either equal to {e} or to to G.

    When H=G, all the cyclic subgroups of the elements of G equal to G (because there are no proper subgroups of G). The question says that we have to show that such a group has order p, where p is prime.

    I tried to use contradiction. My proof tried to show that such a group (where H=G) can exist without have order p (which is a contradiction of course).

    So G = {e, a, a^2, ... ,a^(n-1)}. Since n is nonprime, there exist two integers q and b (where q=/=1 or n and b=/=1 or n), such that n=qb.

    Now I have to prove that all cyclic groups in G are equal to G (since G has no proper subgroups). I chose to look at a^b (we know that a^b is in G, since b < n-1 = qb-1) and show that it cannot equal to G, since there is no integer k, such that kb=qb-1 (mod n).

    This is how I tried to show it:

    kb=qb-1 (mod n) ==> n divides qb-1-kb ==> there exists an integer "c", such that nc=qb-1-kb. So...

    nc=qb-1-kb
    (qb)c= b(q-k)-1

    We know that b(q-k) - 1 < b(q-k) < qb < (qb)c. So b(q-k)-1 < (qb)c. In other words, this is an inequality. So my assumption that there exists a "c" such that nc=qb-1-kb is wrong. Which means that there is no k such that kb=qb-1 (mod n). Which, in turn, means that the cyclic subgroup of a^b does not contain the last element of G, which is a^(n-1). So this must be a proper subgroup...but the type of group that is described in the question says there are no proper subgroups. This is a contradiction...

    Do you think my proof is correct? If not, can you tell me where I'm going wrong? Thanks.
    This just seems over-complicated to me.
    • 0 followers
    Online

    ReputationRep:
    Also you need to exclude the case where G has infinite order.
    • Thread Starter
    • 0 followers
    Offline

    ReputationRep:
    (Original post by matt2k8)
    I don't like the bit about justifying that the order of G is prime - you can just say something like -

    Let g be a generator of G. Suppose that |G| is not prime; so |G| = ab for some a,b both at least 2. Then <g^a> is a cyclic subgroup of G with order b.

    (If you think it's too much to just write down that g^a has order b so <g^a> is cyclic of order b, it's enough to show the weaker statement that g^a has order more than one and at most b, so the order of <g^a> is strictly between 2 and b)
    I could not understand how the order of <g^a> has order b...also how does this show that the order of G is prime?

    Thanks in advance.
    • 0 followers
    Online

    ReputationRep:
    (Original post by Artus)
    I could not understand how the order of <g^a> has order b...also how does this show that the order of G is prime?

    Thanks in advance.
    I'm showing that if the order of G is finite but not prime, we can construct a proper subgroup of G.
    • Thread Starter
    • 0 followers
    Offline

    ReputationRep:
    (Original post by matt2k8)
    I'm showing that if the order of G is finite but not prime, we can construct a proper subgroup of G.
    Thanks. Can you also explain why <g^a> needs to have order b?
    • Thread Starter
    • 0 followers
    Offline

    ReputationRep:
    (Original post by matt2k8)
    I don't like the bit about justifying that the order of G is prime - you can just say something like -

    Let g be a generator of G. Suppose that |G| is not prime; so |G| = ab for some a,b both at least 2. Then <g^a> is a cyclic subgroup of G with order b.

    (If you think it's too much to just write down that g^a has order b so <g^a> is cyclic of order b, it's enough to show the weaker statement that g^a has order more than one and at most b, so the order of <g^a> is strictly between 2 and b)
    Actually, I think I undertand why...

    For example, if we have a cyclic group of order 6, then the order of <g^2> is 3...because the order of g^2 is x, where g^2x = g^6 (since g^6 is equal to the identity). Is that right?

    Also, why do we not consider the possibility of G being infinite?
    • 0 followers
    Online

    ReputationRep:
    (Original post by Artus)
    Actually, I think I undertand why...

    For example, if we have a cyclic group of order 6, then the order of <g^2> is 3...because the order of g^2 is x, where g^2x = g^6 (since g^6 is equal to the identity). Is that right?

    Also, why do we not consider the possibility of G being infinite?
    Being really strict - that just shows the order of g^2 is at most 3. The way I'd argue it's exactly 3 is something like; we know as o(g) = 6, g^l = 1 iff 6 divides l. So if h = g^2, h^k = 1 iff 6|2k which happens iff 3|k - so the order of h must be 3.

    We do need to consider the possibility of G being infinite.
    • 2 followers
    Offline

    ReputationRep:
    Please learn how to title threads. You asked exactly the same question recently yet it is hard to find because all of your threads are entitled "Can you check this?", "Can you give me a hint?" or something equally pointless and nonspecific. This is a forum where every thread is asking for help or hints on something... narrow it down a bit - and don't just put "abstract algebra" either. Be as specific as possible so that you only need duplicate your thread title when you duplicate the thread as in this example.

    Try naming the thread, for example, as "A group with no proper subgroups is cyclic of prime order" etc.

    ----------------------------------------------------------------------------------------------------------------------------------------

    Here are the mistakes, which I am almost sure are the same as pointed out last time:

    i) This is only true if G is non-trivial; the trivial group is cyclic but not of prime order.

    ii) You need to prove (rather than assume) that the group is of finite order i.e.

    If a has infinite order, then G is isomorphic to the integers. But then the cyclic subgroup \langle a^n\rangle is a non-trivial proper subgroup for each integer n &gt; 1 equivalent to the subgroups n\mathbb{Z} under the obvious isomorphism G \to \mathbb{Z}. So, a has finite order.

    iii) "Since b < qb-1, a^b must be an element of G."

    Nonsense. Any power of any element of any group is an element of the group. This is by definition of a binary operation (or the closure axiom if you prefer).

    iv) "So there must be an element k in G such that kb= qb-1 (mod n) (this is of course a congruence sign, not an equal sign)"

    You mean, an element k \in \mathbb{Z}.

    v) "We know that b(q-k)-1 < b(q-k) < qb < c(qb). So b(q-k)-1 < c(qb)".

    You don't know whether k or c are positive or negative.
    • Thread Starter
    • 0 followers
    Offline

    ReputationRep:
    (Original post by Jake22)
    Please learn how to title threads. You asked exactly the same question recently yet it is hard to find because all of your threads are entitled "Can you check this?", "Can you give me a hint?" or something equally pointless and nonspecific. This is a forum where every thread is asking for help or hints on something... narrow it down a bit - and don't just put "abstract algebra" either. Be as specific as possible so that you only need duplicate your thread title when you duplicate the thread as in this example.

    Try naming the thread, for example, as "A group with no proper subgroups is cyclic of prime order" etc.

    ----------------------------------------------------------------------------------------------------------------------------------------

    Here are the mistakes, which I am almost sure are the same as pointed out last time:

    i) This is only true if G is non-trivial; the trivial group is cyclic but not of prime order.

    ii) You need to prove (rather than assume) that the group is of finite order i.e.

    If a has infinite order, then G is isomorphic to the integers. But then the cyclic subgroup \langle a^n\rangle is a non-trivial proper subgroup for each integer n &gt; 1 equivalent to the subgroups n\mathbb{Z} under the obvious isomorphism G \to \mathbb{Z}. So, a has finite order.

    iii) "Since b < qb-1, a^b must be an element of G."

    Nonsense. Any power of any element of any group is an element of the group. This is by definition of a binary operation (or the closure axiom if you prefer).

    iv) "So there must be an element k in G such that kb= qb-1 (mod n) (this is of course a congruence sign, not an equal sign)"

    You mean, an element k \in \mathbb{Z}.

    v) "We know that b(q-k)-1 < b(q-k) < qb < c(qb). So b(q-k)-1 < c(qb)".

    You don't know whether k or c are positive or negative.
    Maybe this is the thread that you mean...http://www.thestudentroom.co.uk/show....php?t=1949593
    • Thread Starter
    • 0 followers
    Offline

    ReputationRep:
    (Original post by Jake22)
    Please learn how to title threads. You asked exactly the same question recently yet it is hard to find because all of your threads are entitled "Can you check this?", "Can you give me a hint?" or something equally pointless and nonspecific. This is a forum where every thread is asking for help or hints on something... narrow it down a bit - and don't just put "abstract algebra" either. Be as specific as possible so that you only need duplicate your thread title when you duplicate the thread as in this example.

    Try naming the thread, for example, as "A group with no proper subgroups is cyclic of prime order" etc.

    ----------------------------------------------------------------------------------------------------------------------------------------

    Here are the mistakes, which I am almost sure are the same as pointed out last time:

    i) This is only true if G is non-trivial; the trivial group is cyclic but not of prime order.

    ii) You need to prove (rather than assume) that the group is of finite order i.e.

    If a has infinite order, then G is isomorphic to the integers. But then the cyclic subgroup \langle a^n\rangle is a non-trivial proper subgroup for each integer n &gt; 1 equivalent to the subgroups n\mathbb{Z} under the obvious isomorphism G \to \mathbb{Z}. So, a has finite order.

    iii) "Since b < qb-1, a^b must be an element of G."

    Nonsense. Any power of any element of any group is an element of the group. This is by definition of a binary operation (or the closure axiom if you prefer).

    iv) "So there must be an element k in G such that kb= qb-1 (mod n) (this is of course a congruence sign, not an equal sign)"

    You mean, an element k \in \mathbb{Z}.

    v) "We know that b(q-k)-1 < b(q-k) < qb < c(qb). So b(q-k)-1 < c(qb)".

    You don't know whether k or c are positive or negative.
    I think I found another way to prove it...

    So, we know that qb-1=kb (mod n). So:

    qb-1-kb=nc
    qb-1-kb=qbc
    qb-kb-qbc=1
    If we divide the whole equation by "b",
    q-k-qc=1/b

    Since we know that q, k, and c are integers, q-k-qc must also be an integer. However 1/b is a fraction, since we know that b is not equal to 1.

    Do you think it is correct now?

    Thanks in advance.
    • 2 followers
    Offline

    ReputationRep:
    (Original post by Artus)
    I think I found another way to prove it...

    So, we know that qb-1=kb (mod n). So:

    qb-1-kb=nc
    qb-1-kb=qbc
    qb-kb-qbc=1
    If we divide the whole equation by "b",
    q-k-qc=1/b

    Since we know that q, k, and c are integers, q-k-qc must also be an integer. However 1/b is a fraction, since we know that b is not equal to 1.

    Do you think it is correct now?

    Thanks in advance.
    Correct modulo the other errors as mentioned above.

    Now that you have worked out how to do it - I would also try to write it out in a more streamlined fashion. Remember, at university level (or even much before that) an answer shouldn't just be right or wrong - one should strive for a good answer. You will also learn much more if you try and write answers well.

Reply

Submit reply

Register

Thanks for posting! You just need to create an account in order to submit the post
  1. this can't be left blank
    that username has been taken, please choose another Forgotten your password?
  2. this can't be left blank
    this email is already registered. Forgotten your password?
  3. this can't be left blank

    6 characters or longer with both numbers and letters is safer

  4. this can't be left empty
    your full birthday is required
  1. By joining you agree to our Ts and Cs, privacy policy and site rules

  2. Slide to join now Processing…

Updated: May 14, 2012
New on TSR

Writing your personal statement

Our free PS builder tool makes it easy

Article updates
Reputation gems:
You get these gems as you gain rep from other members for making good contributions and giving helpful advice.