Results 1 to 3 of 3

Math Help - pigeonhole principle

  1. #1
    ux0
    ux0 is offline
    Junior Member
    Joined
    Oct 2009
    Posts
    58

    pigeonhole principle

    Let G be a Finite group written mlutiplicatively. Prove that if the order of G is odd, then every x \in G has a square root. Conclude the proof with there exists exactly one g \in G with g^2=x


    I think i need to show that squaring is an injective funciton from  G \to G and use the pigeonhole principle...
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by ux0 View Post
    Let G be a Finite group written mlutiplicatively. Prove that if the order of G is odd, then every x \in G has a square root. Conclude the proof with there exists exactly one g \in G with g^2=x


    I think i need to show that squaring is an injective funciton from  G \to G and use the pigeonhole principle...
    let |G|=2n+1. then for every x \in G: \ x^{2n+1}=1, and thus (x^{n+1})^2=x^{2n+2}=x. if g^2=h^2, then g=g^{2n+2}=h^{2n+2}=h.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by ux0 View Post
    Let G be a Finite group written mlutiplicatively. Prove that if the order of G is odd, then every x \in G has a square root. Conclude the proof with there exists exactly one g \in G with g^2=x


    I think i need to show that squaring is an injective funciton from  G \to G and use the pigeonhole principle...

    Well, if by "using the pigeonhole principle" you mean that a function from a finite set to itself is injective iff it is onto then yes: you need that.

    Now define f:G \rightarrow G\,,\,\,f(g)=g^2 . Since the order of G is odd the function is injective (because if g^2=x^2 then, as g has odd order, g^{2k-1}=1 \Longrightarrow 1=\left(g^2\right)^kg^{-1}=x^{2k}g^{-1} \Longrightarrow g=x^{2k} \Longrightarrow x^2=g^2=x^{4k} and then we get x has even order, which is impossible in a group of odd order) we're done.

    Tonio
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. help me with pigeonhole principle #2
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 31st 2009, 11:23 PM
  2. help me with pigeonhole principle #1
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 31st 2009, 03:58 PM
  3. Pigeonhole principle
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: January 31st 2009, 03:59 PM
  4. Pigeonhole Principle
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: August 30th 2007, 03:15 PM
  5. Pigeonhole Principle
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: January 23rd 2006, 06:09 PM

Search Tags


/mathhelpforum @mathhelpforum