# pigeonhole principle

• Oct 24th 2009, 10:05 AM
ux0
pigeonhole principle
Let G be a Finite group written mlutiplicatively. Prove that if the order of G is odd, then every $\displaystyle x \in G$ has a square root. Conclude the proof with there exists exactly one $\displaystyle g \in G$ with $\displaystyle g^2=x$

I think i need to show that squaring is an injective funciton from $\displaystyle G \to G$ and use the pigeonhole principle...
• Oct 24th 2009, 12:01 PM
NonCommAlg
Quote:

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

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

let $\displaystyle |G|=2n+1.$ then for every $\displaystyle x \in G: \ x^{2n+1}=1,$ and thus $\displaystyle (x^{n+1})^2=x^{2n+2}=x.$ if $\displaystyle g^2=h^2,$ then $\displaystyle g=g^{2n+2}=h^{2n+2}=h.$
• Oct 24th 2009, 12:46 PM
tonio
Quote:

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

I think i need to show that squaring is an injective funciton from $\displaystyle 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 $\displaystyle f:G \rightarrow G\,,\,\,f(g)=g^2$ . Since the order of G is odd the function is injective (because if $\displaystyle g^2=x^2$ then, as g has odd order, $\displaystyle 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