Results 1 to 5 of 5

Math Help - Cannot find the contradiction

  1. #1
    Senior Member slevvio's Avatar
    Joined
    Oct 2007
    Posts
    347

    Cannot find the contradiction

    Hello all. I have something in which there must be a contradiction but I cannot find it.

    So let \phi be the usual Euler phi/totient function, and let G be a finite group. Then we have

    (1) \phi_G(d) = \phi(d) \cdot q(d)
    where q(d) = the number of cyclic subgroups of order d and \phi_G(d) = the number of elements of order d in G.

    Then we also have the theorem
    (2) \displaystyle\sum_{d | n} \phi(d) = n.
    But I have a theorem in my notes

    which states \displaystyle\sum_{d | |G|} \phi_G (d) = |G|. But by (1), this is equivalent to the statement \displaystyle\sum_{d | |G|} \phi(d) q(d) = |G|.

    But doesn't this contradict (2) ? Unless q(d) = 1 \text{ whenever } \phi(d) \not= 0 which cannot be true otherwise there would be no point looking at \phi_G(d). Can anyone help?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Actually, it turns out that q(d) may be 0 for some d| |G|.

    For example: a finite group G is not cyclic iff q(|G|) = 0.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by slevvio View Post
    Hello all. I have something in which there must be a contradiction but I cannot find it.

    So let \phi be the usual Euler phi/totient function, and let G be a finite group. Then we have

    (1) \phi_G(d) = \phi(d) \cdot q(d)
    where q(d) = the number of cyclic subgroups of order d and \phi_G(d) = the number of elements of order d in G.

    Then we also have the theorem
    (2) \displaystyle\sum_{d | n} \phi(d) = n.
    But I have a theorem in my notes

    which states \displaystyle\sum_{d | |G|} \phi_G (d) = |G|. But by (1), this is equivalent to the statement \displaystyle\sum_{d | |G|} \phi(d) q(d) = |G|.

    But doesn't this contradict (2) ? Unless q(d) = 1 \text{ whenever } \phi(d) \not= 0 which cannot be true otherwise there would be no point looking at \phi_G(d). Can anyone help?
    It's possible  q(d)=0 , in fact it happens often.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by slevvio View Post
    Hello all. I have something in which there must be a contradiction but I cannot find it.

    So let \phi be the usual Euler phi/totient function, and let G be a finite group. Then we have

    (1) \phi_G(d) = \phi(d) \cdot q(d)
    where q(d) = the number of cyclic subgroups of order d and \phi_G(d) = the number of elements of order d in G.

    Then we also have the theorem
    (2) \displaystyle\sum_{d | n} \phi(d) = n.
    But I have a theorem in my notes

    which states \displaystyle\sum_{d | |G|} \phi_G (d) = |G|. But by (1), this is equivalent to the statement \displaystyle\sum_{d | |G|} \phi(d) q(d) = |G|.

    But doesn't this contradict (2) ? Unless q(d) = 1 \text{ whenever } \phi(d) \not= 0 which cannot be true otherwise there would be no point looking at \phi_G(d). Can anyone help?
    I don't particularly understand you're confusion, I don't see an immediate contradiction. One way that someone could define this is to define the relation \overset{\text{gen}}{\sim} on G by g\overset{\text{gen}}{\sim}h if and only if \langle g\rangle=\langle h\rangle. If one then calls the equivalence classes of this (clearly equivalence) relation \text{gen}(g) then one has that \displaystyle G=\biguplus_{g\in\Gamma}\text{gen}(g) where \Gamma is a set which contains one representative from each equivalence class. It follows then that \displaystyle |G|=\sum_{g\in\Gamma}\#\left(\text{gen}(g)\right) but it's not hard to prove that \#\left(\text{gen}(g)\right)=\varphi\left(|g|\righ  t)q(|g|) (using your notation) and thus, we may conclude that \displaystyle |G|=\sum_{g\in\Gamma}\varphi(|g|)q(|g|) but it shouldn't be hard to convince yourself that this can be written (recalling Lagrange's theorem and the fact that even if the group does not contain any cyclic subgroups of order d\mid n then one may add the term since it's zero) as \displaystyle |G|=\sum_{d\mid |G|}\varphi(d)q(d). So, this in particular proves that \displaystyle \sum_{d\mid n}\varphi(g)=n by considering that \mathbb{Z}/n\mathbb{Z} has exactly one subgroup (and of course this implies one cyclic subgroup) for each divisor of n. How does using these facts contradict anything?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member slevvio's Avatar
    Joined
    Oct 2007
    Posts
    347
    I just got confused since q(d) may = 0 while \phi(d) doesn't
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. contradiction help
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: March 1st 2010, 11:05 PM
  2. Proof by contradiction
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 5th 2010, 04:17 PM
  3. contradiction
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 18th 2008, 08:52 AM
  4. contradiction problem
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: May 25th 2008, 07:54 AM
  5. Proof by Contradiction
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 8th 2007, 05:51 AM

Search Tags


/mathhelpforum @mathhelpforum