Putnam 2007 A5: Finite group $n$ elements order $p$, prove either $n=0$ or $p$ divides $n+1$

Clash Royale CLAN TAG#URR8PPP

up vote
13
down vote

favorite

4

Putnam 2007 Question A5:

"Suppose that a finite group has exactly $n$ elements of order $p$, where $p$ is a prime. Prove that either $n=0$ or $p$ divides $n+1$."

I split this problem into two cases: where $p$ divides $|G|=m$, and where $p$ does not divide $m$. The latter case is trivial - by Lagrange's Theorem, $n=0$ as the order of an element must divide the order of the group. The first case appears more complicated and my idea is to use Sylow Theory, and I came across an interesting solution using this on https://blogs.haverford.edu/mathproblemsolving/files/2010/05/Putnam-2007-Solutions.pdf:

"There are 1 + kp Sylow p-subgroups and, because they are all conjugate and every element of order p is contained in some Sylow p-subroup, they partition the n elements of order p into 1 + kp equal-size collections. The number of elements of order p in any p-group is always one less than a power of p, implying n + 1 ≡ (1 + kp)(-1) + 1 ≡ 0 modulo p."

The places I am stuck are:

1) Why the fact that all Sylow p-subgroups being conjugate and every element of order $p$ contained in some Sylow p-subgroup (I understand why both these facts are true), implies that the Sylow p-subgroups partition the $n$ elements of order $p$ into $1+kp$ equal-size collections - heck I don't even understand what is meant by this...

2) Why the number of elements of order $p$ in any p-group is always one less than a power of p.

If anyone has other ways to show that $p$ dividing $m$ implies that $p$ divides $n+1$, that would also be greatly appreciated :)

Thanks

abstract-algebra group-theory finite-groups contest-math sylow-theory

share|cite|improve this question

asked Jul 30 at 23:55

Daniele1234

716215

add a comment | 

up vote
13
down vote

favorite

4

Putnam 2007 Question A5:

"Suppose that a finite group has exactly $n$ elements of order $p$, where $p$ is a prime. Prove that either $n=0$ or $p$ divides $n+1$."

I split this problem into two cases: where $p$ divides $|G|=m$, and where $p$ does not divide $m$. The latter case is trivial - by Lagrange's Theorem, $n=0$ as the order of an element must divide the order of the group. The first case appears more complicated and my idea is to use Sylow Theory, and I came across an interesting solution using this on https://blogs.haverford.edu/mathproblemsolving/files/2010/05/Putnam-2007-Solutions.pdf:

"There are 1 + kp Sylow p-subgroups and, because they are all conjugate and every element of order p is contained in some Sylow p-subroup, they partition the n elements of order p into 1 + kp equal-size collections. The number of elements of order p in any p-group is always one less than a power of p, implying n + 1 ≡ (1 + kp)(-1) + 1 ≡ 0 modulo p."

The places I am stuck are:

1) Why the fact that all Sylow p-subgroups being conjugate and every element of order $p$ contained in some Sylow p-subgroup (I understand why both these facts are true), implies that the Sylow p-subgroups partition the $n$ elements of order $p$ into $1+kp$ equal-size collections - heck I don't even understand what is meant by this...

2) Why the number of elements of order $p$ in any p-group is always one less than a power of p.

If anyone has other ways to show that $p$ dividing $m$ implies that $p$ divides $n+1$, that would also be greatly appreciated :)

Thanks

abstract-algebra group-theory finite-groups contest-math sylow-theory

share|cite|improve this question

asked Jul 30 at 23:55

Daniele1234

716215

add a comment | 

up vote
13
down vote

favorite

4

up vote
13
down vote

favorite

4

4

Putnam 2007 Question A5:

"Suppose that a finite group has exactly $n$ elements of order $p$, where $p$ is a prime. Prove that either $n=0$ or $p$ divides $n+1$."

I split this problem into two cases: where $p$ divides $|G|=m$, and where $p$ does not divide $m$. The latter case is trivial - by Lagrange's Theorem, $n=0$ as the order of an element must divide the order of the group. The first case appears more complicated and my idea is to use Sylow Theory, and I came across an interesting solution using this on https://blogs.haverford.edu/mathproblemsolving/files/2010/05/Putnam-2007-Solutions.pdf:

"There are 1 + kp Sylow p-subgroups and, because they are all conjugate and every element of order p is contained in some Sylow p-subroup, they partition the n elements of order p into 1 + kp equal-size collections. The number of elements of order p in any p-group is always one less than a power of p, implying n + 1 ≡ (1 + kp)(-1) + 1 ≡ 0 modulo p."

The places I am stuck are:

1) Why the fact that all Sylow p-subgroups being conjugate and every element of order $p$ contained in some Sylow p-subgroup (I understand why both these facts are true), implies that the Sylow p-subgroups partition the $n$ elements of order $p$ into $1+kp$ equal-size collections - heck I don't even understand what is meant by this...

2) Why the number of elements of order $p$ in any p-group is always one less than a power of p.

If anyone has other ways to show that $p$ dividing $m$ implies that $p$ divides $n+1$, that would also be greatly appreciated :)

Thanks

abstract-algebra group-theory finite-groups contest-math sylow-theory

share|cite|improve this question

asked Jul 30 at 23:55

Daniele1234

716215

Putnam 2007 Question A5:

"Suppose that a finite group has exactly $n$ elements of order $p$, where $p$ is a prime. Prove that either $n=0$ or $p$ divides $n+1$."

I split this problem into two cases: where $p$ divides $|G|=m$, and where $p$ does not divide $m$. The latter case is trivial - by Lagrange's Theorem, $n=0$ as the order of an element must divide the order of the group. The first case appears more complicated and my idea is to use Sylow Theory, and I came across an interesting solution using this on https://blogs.haverford.edu/mathproblemsolving/files/2010/05/Putnam-2007-Solutions.pdf:

"There are 1 + kp Sylow p-subgroups and, because they are all conjugate and every element of order p is contained in some Sylow p-subroup, they partition the n elements of order p into 1 + kp equal-size collections. The number of elements of order p in any p-group is always one less than a power of p, implying n + 1 ≡ (1 + kp)(-1) + 1 ≡ 0 modulo p."

The places I am stuck are:

1) Why the fact that all Sylow p-subgroups being conjugate and every element of order $p$ contained in some Sylow p-subgroup (I understand why both these facts are true), implies that the Sylow p-subgroups partition the $n$ elements of order $p$ into $1+kp$ equal-size collections - heck I don't even understand what is meant by this...

2) Why the number of elements of order $p$ in any p-group is always one less than a power of p.

If anyone has other ways to show that $p$ dividing $m$ implies that $p$ divides $n+1$, that would also be greatly appreciated :)

Thanks

abstract-algebra group-theory finite-groups contest-math sylow-theory

share|cite|improve this question

asked Jul 30 at 23:55

Daniele1234

716215

share|cite|improve this question

share|cite|improve this question

asked Jul 30 at 23:55

Daniele1234

716215

asked Jul 30 at 23:55

Daniele1234

716215

asked Jul 30 at 23:55

Daniele1234

716215

716215

add a comment | 

add a comment | 

3 Answers
3

active

oldest

votes

up vote
14
down vote



accepted

Here is a proof of the result, via an (famous/very clever/pretty) idea James McKay used to prove Cauchy's theorem.

Let $S$ denote the set of $p$-tuples $(a_1, a_2, cdots, a_p)$ where $a_i in G$ and $a_1 a_2 a_3 cdots a_p = 1$. Note that $mathbbZ/pmathbbZ$ acts on $S$ by cyclic rotations. Thus, we have $$|S| = #textorbits of size 1 + #textorbits of size p cdot p $$ Orbits of size 1 correspond to tuples of the form $(x, x, x, cdots, x)$, i.e. elements $xin G$ of order $p$, excepting the orbit corresponding to the trivial tuple $(1, 1, 1, cdots 1)$. Thus, $$#textorbits of size 1 = #textelements of order p + 1 = n+1$$ On the other hand, note that $|S| = |G|^p-1$ because the first $p-1$ elements of any $p$-tuple can be chosen totally arbitrarily, and then the last element of the tuple is fixed. Taking the equation for $|S|$ modulo $p$, we see that if $p$ divides $|G|$, then $p$ divides $n+1$, as desired.

share|cite|improve this answer

edited Jul 31 at 15:30

answered Jul 31 at 0:14

Sameer Kailasa

5,24621743

• 
  
  
  

  
  

  
  
  
  
  
  

  
  First, thank you very much for your answer. I have read that $S$ is invariant under cyclic permutation, but do you know why, as $G$ Is not necessarily abelian...
  – Daniele1234
  Jul 31 at 0:27
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Yes -- suppose $(a_1, a_2, cdots, a_p)$ is a tuple with $a_1 a_2 cdots a_p = 1$. Then we have $a_2 a_3 cdots a_p = a_1^-1$ by left-multiplying with $a_1^-1$. Then, right-multiplying by $a_1$ gives $a_2 a_3 cdots a_p a_1 = 1$. So, $(a_2, a_3, cdots, a_p, a_1)$ is another tuple in $S$. Continuing in this manner, we see any cyclic shift of $(a_1, cdots, a_p)$ will yield a tuple in $S$.
  – Sameer Kailasa
  Jul 31 at 0:31
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  One for The Book. Beautiful proof!
  – Mike
  Jul 31 at 0:33
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  I use McKay’s proof all the time in my algebra and crypto classes. One of the all time greats. It’s so clear.
  – Randall
  Jul 31 at 0:47
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @SameerKailasa Where does one get the formula for the order of S as you have above - why are there no orbits of size $p/2$ for example...
  – Daniele1234
  Jul 31 at 0:54
  

  
  
  
  

 | 
show 2 more comments

up vote
1
down vote

First of all by the Second Sylow Theorem we have that all Sylow p-groups are conjugates of each other. Furthermore we have that conjugation leaves the order of the element intact. For example let $P_1$ and $P_2$ be any Sylow p-groups. Then $exists g in G$ s.t. $gP_1g^-1 = P_2$. Also if $x$ is an element of $P_1$ of order $p$, then $gxg^-1$ is an element of $P_2$ of order $p$. In other word this means that each Sylow p-group have the same number of elements of order $p$.

Thus as we the number of Sylow p-subgroups is $1 pmod p$ the $n$ elements are partitioned into $kp+1$ Sylow p-subgroups, each containing the same number of elements.

For the second part you can use the notation used in the Sameer's answer and get that $n+1 equiv |S| equiv 0 pmod p$

share|cite|improve this answer

answered Jul 31 at 0:27

Stefan4024

27.8k52974

add a comment | 

up vote
1
down vote

While it is the case that the number of elements of order $p$ of a $p$-group is congruent to $-1$ modulo $p$, it is not true that the number of elements of order $p$ of a $p$-group must be of the form $p^k-1$ for some $kinmathbbZ_>0$. The solution you have is not entirely correct.

Here is a counterexample. Consider the dihedral group $$beginalignG&:=D_4=biglangle a,b,big|,a^4=1,,,,b^2=1,,text and bab^-1=a^-1bigrangle
\&=big,rin0,1,2,3text and sin0,1big,.endalign$$
Note that $|G|=8=2^3$. The elements of order $2$ of $G$ are listed below:
$$a^2,b,ab,a^2b,a^3b,.$$
That is, there are exactly $5$ elements of order $2$ in $G$. Clearly, $5equiv-1pmod2$, but it is not of the form $2^k-1$ for any $kinmathbbZ_>0$. The remaining $2$ non-identity elements of $G$ are $a$ and $a^3$, which are of order $4$.

---

Here is an alternative proof that the number $n$ of elements of order $p$ of a $p$-group $G$ satisfies $$nequiv -1pmodp,.$$ Consider the set $A$ of elements of $G$ containing all $xin G$ such that $x^p=1$. Clearly, $n=|A|-1$. We claim that $p$ divides $|A|$.

Let $Z$ denote the center of $G$. We note that the order of $Acap Z$ must be a power of $p$, being a subgroup of an abelian $p$-group $Ztrianglelefteq G$. Thus, $p$ divides $|Acap Z|$ (as every $p$-group has a nontrivial center, which contains an element of order $p$). It remains to verify that $p$ divides $|Asetminus Z|=|A|-|Acap Z|$.

We can partition $B:=Asetminus Z$ into orbits of elements of $B$ under conjugation in $G$. Clearly, any conjugate of an element of $B$ is in $B$. Due to the Orbit-Stabilizer Theorem, the size of each orbit is a power of $p$, and since the orbit contains a noncentral element, its size is larger than $1$. Consequently, every orbit of elements in $B$ is of size $p^k$ for some integer $kgeq 1$. This proves that $|B|$ is divisible by $p$. (In fact, $|B|$ is also divisible by $p-1$.)

---

As an example, with $G$ being the dihedral group $D_4$ as above, we have $A=(Acap Z)cup B$, where
$$Acap Z=Z=big1,a^4big
text and B=bigb,ab,a^2b,a^3bbig,.$$ The partition of $B$ into conjugacy orbits (or conjugacy classes) is
$$b,a^2bcupab,a^3b,.$$

share|cite|improve this answer

edited Jul 31 at 16:25

answered Jul 31 at 6:28

Batominovski

22.8k22776

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  I think we must write $|A setminus Z| = |A| - |Z cap A|$, as $Z$ need not sit wholly in $A$. (But the proof still goes through perfectly after this)
  – Sameer Kailasa
  Jul 31 at 16:20
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  OOppps, you are right. Sorry and thanks!
  – Batominovski
  Jul 31 at 16:22
  
  

  
  
  
  

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
convertImagesToLinks: true,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2867522%2fputnam-2007-a5-finite-group-n-elements-order-p-prove-either-n-0-or-p-d%23new-answer', 'question_page');

);

Post as a guest

Name Email

3 Answers
3

active

oldest

votes

3 Answers
3

active

oldest

votes

active

oldest

votes

active

oldest

votes

up vote
14
down vote



accepted

Here is a proof of the result, via an (famous/very clever/pretty) idea James McKay used to prove Cauchy's theorem.

Let $S$ denote the set of $p$-tuples $(a_1, a_2, cdots, a_p)$ where $a_i in G$ and $a_1 a_2 a_3 cdots a_p = 1$. Note that $mathbbZ/pmathbbZ$ acts on $S$ by cyclic rotations. Thus, we have $$|S| = #textorbits of size 1 + #textorbits of size p cdot p $$ Orbits of size 1 correspond to tuples of the form $(x, x, x, cdots, x)$, i.e. elements $xin G$ of order $p$, excepting the orbit corresponding to the trivial tuple $(1, 1, 1, cdots 1)$. Thus, $$#textorbits of size 1 = #textelements of order p + 1 = n+1$$ On the other hand, note that $|S| = |G|^p-1$ because the first $p-1$ elements of any $p$-tuple can be chosen totally arbitrarily, and then the last element of the tuple is fixed. Taking the equation for $|S|$ modulo $p$, we see that if $p$ divides $|G|$, then $p$ divides $n+1$, as desired.

share|cite|improve this answer

edited Jul 31 at 15:30

answered Jul 31 at 0:14

Sameer Kailasa

5,24621743

• 
  
  
  

  
  

  
  
  
  
  
  

  
  First, thank you very much for your answer. I have read that $S$ is invariant under cyclic permutation, but do you know why, as $G$ Is not necessarily abelian...
  – Daniele1234
  Jul 31 at 0:27
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Yes -- suppose $(a_1, a_2, cdots, a_p)$ is a tuple with $a_1 a_2 cdots a_p = 1$. Then we have $a_2 a_3 cdots a_p = a_1^-1$ by left-multiplying with $a_1^-1$. Then, right-multiplying by $a_1$ gives $a_2 a_3 cdots a_p a_1 = 1$. So, $(a_2, a_3, cdots, a_p, a_1)$ is another tuple in $S$. Continuing in this manner, we see any cyclic shift of $(a_1, cdots, a_p)$ will yield a tuple in $S$.
  – Sameer Kailasa
  Jul 31 at 0:31
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  One for The Book. Beautiful proof!
  – Mike
  Jul 31 at 0:33
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  I use McKay’s proof all the time in my algebra and crypto classes. One of the all time greats. It’s so clear.
  – Randall
  Jul 31 at 0:47
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @SameerKailasa Where does one get the formula for the order of S as you have above - why are there no orbits of size $p/2$ for example...
  – Daniele1234
  Jul 31 at 0:54
  

  
  
  
  

 | 
show 2 more comments

up vote
14
down vote



accepted

Here is a proof of the result, via an (famous/very clever/pretty) idea James McKay used to prove Cauchy's theorem.

Let $S$ denote the set of $p$-tuples $(a_1, a_2, cdots, a_p)$ where $a_i in G$ and $a_1 a_2 a_3 cdots a_p = 1$. Note that $mathbbZ/pmathbbZ$ acts on $S$ by cyclic rotations. Thus, we have $$|S| = #textorbits of size 1 + #textorbits of size p cdot p $$ Orbits of size 1 correspond to tuples of the form $(x, x, x, cdots, x)$, i.e. elements $xin G$ of order $p$, excepting the orbit corresponding to the trivial tuple $(1, 1, 1, cdots 1)$. Thus, $$#textorbits of size 1 = #textelements of order p + 1 = n+1$$ On the other hand, note that $|S| = |G|^p-1$ because the first $p-1$ elements of any $p$-tuple can be chosen totally arbitrarily, and then the last element of the tuple is fixed. Taking the equation for $|S|$ modulo $p$, we see that if $p$ divides $|G|$, then $p$ divides $n+1$, as desired.

share|cite|improve this answer

edited Jul 31 at 15:30

answered Jul 31 at 0:14

Sameer Kailasa

5,24621743

• 
  
  
  

  
  

  
  
  
  
  
  

  
  First, thank you very much for your answer. I have read that $S$ is invariant under cyclic permutation, but do you know why, as $G$ Is not necessarily abelian...
  – Daniele1234
  Jul 31 at 0:27
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Yes -- suppose $(a_1, a_2, cdots, a_p)$ is a tuple with $a_1 a_2 cdots a_p = 1$. Then we have $a_2 a_3 cdots a_p = a_1^-1$ by left-multiplying with $a_1^-1$. Then, right-multiplying by $a_1$ gives $a_2 a_3 cdots a_p a_1 = 1$. So, $(a_2, a_3, cdots, a_p, a_1)$ is another tuple in $S$. Continuing in this manner, we see any cyclic shift of $(a_1, cdots, a_p)$ will yield a tuple in $S$.
  – Sameer Kailasa
  Jul 31 at 0:31
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  One for The Book. Beautiful proof!
  – Mike
  Jul 31 at 0:33
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  I use McKay’s proof all the time in my algebra and crypto classes. One of the all time greats. It’s so clear.
  – Randall
  Jul 31 at 0:47
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @SameerKailasa Where does one get the formula for the order of S as you have above - why are there no orbits of size $p/2$ for example...
  – Daniele1234
  Jul 31 at 0:54
  

  
  
  
  

 | 
show 2 more comments

up vote
14
down vote



accepted

up vote
14
down vote



accepted

Here is a proof of the result, via an (famous/very clever/pretty) idea James McKay used to prove Cauchy's theorem.

Let $S$ denote the set of $p$-tuples $(a_1, a_2, cdots, a_p)$ where $a_i in G$ and $a_1 a_2 a_3 cdots a_p = 1$. Note that $mathbbZ/pmathbbZ$ acts on $S$ by cyclic rotations. Thus, we have $$|S| = #textorbits of size 1 + #textorbits of size p cdot p $$ Orbits of size 1 correspond to tuples of the form $(x, x, x, cdots, x)$, i.e. elements $xin G$ of order $p$, excepting the orbit corresponding to the trivial tuple $(1, 1, 1, cdots 1)$. Thus, $$#textorbits of size 1 = #textelements of order p + 1 = n+1$$ On the other hand, note that $|S| = |G|^p-1$ because the first $p-1$ elements of any $p$-tuple can be chosen totally arbitrarily, and then the last element of the tuple is fixed. Taking the equation for $|S|$ modulo $p$, we see that if $p$ divides $|G|$, then $p$ divides $n+1$, as desired.

share|cite|improve this answer

edited Jul 31 at 15:30

answered Jul 31 at 0:14

Sameer Kailasa

5,24621743

Here is a proof of the result, via an (famous/very clever/pretty) idea James McKay used to prove Cauchy's theorem.

Let $S$ denote the set of $p$-tuples $(a_1, a_2, cdots, a_p)$ where $a_i in G$ and $a_1 a_2 a_3 cdots a_p = 1$. Note that $mathbbZ/pmathbbZ$ acts on $S$ by cyclic rotations. Thus, we have $$|S| = #textorbits of size 1 + #textorbits of size p cdot p $$ Orbits of size 1 correspond to tuples of the form $(x, x, x, cdots, x)$, i.e. elements $xin G$ of order $p$, excepting the orbit corresponding to the trivial tuple $(1, 1, 1, cdots 1)$. Thus, $$#textorbits of size 1 = #textelements of order p + 1 = n+1$$ On the other hand, note that $|S| = |G|^p-1$ because the first $p-1$ elements of any $p$-tuple can be chosen totally arbitrarily, and then the last element of the tuple is fixed. Taking the equation for $|S|$ modulo $p$, we see that if $p$ divides $|G|$, then $p$ divides $n+1$, as desired.

share|cite|improve this answer

edited Jul 31 at 15:30

answered Jul 31 at 0:14

Sameer Kailasa

5,24621743

share|cite|improve this answer

share|cite|improve this answer

edited Jul 31 at 15:30

edited Jul 31 at 15:30

edited Jul 31 at 15:30

answered Jul 31 at 0:14

Sameer Kailasa

5,24621743

answered Jul 31 at 0:14

Sameer Kailasa

5,24621743

answered Jul 31 at 0:14

Sameer Kailasa

5,24621743

5,24621743

• 
  
  
  

  
  

  
  
  
  
  
  

  
  First, thank you very much for your answer. I have read that $S$ is invariant under cyclic permutation, but do you know why, as $G$ Is not necessarily abelian...
  – Daniele1234
  Jul 31 at 0:27
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Yes -- suppose $(a_1, a_2, cdots, a_p)$ is a tuple with $a_1 a_2 cdots a_p = 1$. Then we have $a_2 a_3 cdots a_p = a_1^-1$ by left-multiplying with $a_1^-1$. Then, right-multiplying by $a_1$ gives $a_2 a_3 cdots a_p a_1 = 1$. So, $(a_2, a_3, cdots, a_p, a_1)$ is another tuple in $S$. Continuing in this manner, we see any cyclic shift of $(a_1, cdots, a_p)$ will yield a tuple in $S$.
  – Sameer Kailasa
  Jul 31 at 0:31
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  One for The Book. Beautiful proof!
  – Mike
  Jul 31 at 0:33
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  I use McKay’s proof all the time in my algebra and crypto classes. One of the all time greats. It’s so clear.
  – Randall
  Jul 31 at 0:47
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @SameerKailasa Where does one get the formula for the order of S as you have above - why are there no orbits of size $p/2$ for example...
  – Daniele1234
  Jul 31 at 0:54
  

  
  
  
  

 | 
show 2 more comments

• 
  
  
  

  
  

  
  
  
  
  
  

  
  First, thank you very much for your answer. I have read that $S$ is invariant under cyclic permutation, but do you know why, as $G$ Is not necessarily abelian...
  – Daniele1234
  Jul 31 at 0:27
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Yes -- suppose $(a_1, a_2, cdots, a_p)$ is a tuple with $a_1 a_2 cdots a_p = 1$. Then we have $a_2 a_3 cdots a_p = a_1^-1$ by left-multiplying with $a_1^-1$. Then, right-multiplying by $a_1$ gives $a_2 a_3 cdots a_p a_1 = 1$. So, $(a_2, a_3, cdots, a_p, a_1)$ is another tuple in $S$. Continuing in this manner, we see any cyclic shift of $(a_1, cdots, a_p)$ will yield a tuple in $S$.
  – Sameer Kailasa
  Jul 31 at 0:31
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  One for The Book. Beautiful proof!
  – Mike
  Jul 31 at 0:33
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  I use McKay’s proof all the time in my algebra and crypto classes. One of the all time greats. It’s so clear.
  – Randall
  Jul 31 at 0:47
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @SameerKailasa Where does one get the formula for the order of S as you have above - why are there no orbits of size $p/2$ for example...
  – Daniele1234
  Jul 31 at 0:54
  

  
  
  
  

First, thank you very much for your answer. I have read that $S$ is invariant under cyclic permutation, but do you know why, as $G$ Is not necessarily abelian...
– Daniele1234
Jul 31 at 0:27

First, thank you very much for your answer. I have read that $S$ is invariant under cyclic permutation, but do you know why, as $G$ Is not necessarily abelian...
– Daniele1234
Jul 31 at 0:27

Yes -- suppose $(a_1, a_2, cdots, a_p)$ is a tuple with $a_1 a_2 cdots a_p = 1$. Then we have $a_2 a_3 cdots a_p = a_1^-1$ by left-multiplying with $a_1^-1$. Then, right-multiplying by $a_1$ gives $a_2 a_3 cdots a_p a_1 = 1$. So, $(a_2, a_3, cdots, a_p, a_1)$ is another tuple in $S$. Continuing in this manner, we see any cyclic shift of $(a_1, cdots, a_p)$ will yield a tuple in $S$.
– Sameer Kailasa
Jul 31 at 0:31

Yes -- suppose $(a_1, a_2, cdots, a_p)$ is a tuple with $a_1 a_2 cdots a_p = 1$. Then we have $a_2 a_3 cdots a_p = a_1^-1$ by left-multiplying with $a_1^-1$. Then, right-multiplying by $a_1$ gives $a_2 a_3 cdots a_p a_1 = 1$. So, $(a_2, a_3, cdots, a_p, a_1)$ is another tuple in $S$. Continuing in this manner, we see any cyclic shift of $(a_1, cdots, a_p)$ will yield a tuple in $S$.
– Sameer Kailasa
Jul 31 at 0:31

One for The Book. Beautiful proof!
– Mike
Jul 31 at 0:33

One for The Book. Beautiful proof!
– Mike
Jul 31 at 0:33

I use McKay’s proof all the time in my algebra and crypto classes. One of the all time greats. It’s so clear.
– Randall
Jul 31 at 0:47

I use McKay’s proof all the time in my algebra and crypto classes. One of the all time greats. It’s so clear.
– Randall
Jul 31 at 0:47

@SameerKailasa Where does one get the formula for the order of S as you have above - why are there no orbits of size $p/2$ for example...
– Daniele1234
Jul 31 at 0:54

@SameerKailasa Where does one get the formula for the order of S as you have above - why are there no orbits of size $p/2$ for example...
– Daniele1234
Jul 31 at 0:54

 | 
show 2 more comments

up vote
1
down vote

First of all by the Second Sylow Theorem we have that all Sylow p-groups are conjugates of each other. Furthermore we have that conjugation leaves the order of the element intact. For example let $P_1$ and $P_2$ be any Sylow p-groups. Then $exists g in G$ s.t. $gP_1g^-1 = P_2$. Also if $x$ is an element of $P_1$ of order $p$, then $gxg^-1$ is an element of $P_2$ of order $p$. In other word this means that each Sylow p-group have the same number of elements of order $p$.

Thus as we the number of Sylow p-subgroups is $1 pmod p$ the $n$ elements are partitioned into $kp+1$ Sylow p-subgroups, each containing the same number of elements.

For the second part you can use the notation used in the Sameer's answer and get that $n+1 equiv |S| equiv 0 pmod p$

share|cite|improve this answer

answered Jul 31 at 0:27

Stefan4024

27.8k52974

add a comment | 

up vote
1
down vote

First of all by the Second Sylow Theorem we have that all Sylow p-groups are conjugates of each other. Furthermore we have that conjugation leaves the order of the element intact. For example let $P_1$ and $P_2$ be any Sylow p-groups. Then $exists g in G$ s.t. $gP_1g^-1 = P_2$. Also if $x$ is an element of $P_1$ of order $p$, then $gxg^-1$ is an element of $P_2$ of order $p$. In other word this means that each Sylow p-group have the same number of elements of order $p$.

Thus as we the number of Sylow p-subgroups is $1 pmod p$ the $n$ elements are partitioned into $kp+1$ Sylow p-subgroups, each containing the same number of elements.

For the second part you can use the notation used in the Sameer's answer and get that $n+1 equiv |S| equiv 0 pmod p$

share|cite|improve this answer

answered Jul 31 at 0:27

Stefan4024

27.8k52974

add a comment | 

up vote
1
down vote

up vote
1
down vote

First of all by the Second Sylow Theorem we have that all Sylow p-groups are conjugates of each other. Furthermore we have that conjugation leaves the order of the element intact. For example let $P_1$ and $P_2$ be any Sylow p-groups. Then $exists g in G$ s.t. $gP_1g^-1 = P_2$. Also if $x$ is an element of $P_1$ of order $p$, then $gxg^-1$ is an element of $P_2$ of order $p$. In other word this means that each Sylow p-group have the same number of elements of order $p$.

Thus as we the number of Sylow p-subgroups is $1 pmod p$ the $n$ elements are partitioned into $kp+1$ Sylow p-subgroups, each containing the same number of elements.

For the second part you can use the notation used in the Sameer's answer and get that $n+1 equiv |S| equiv 0 pmod p$

share|cite|improve this answer

answered Jul 31 at 0:27

Stefan4024

27.8k52974

First of all by the Second Sylow Theorem we have that all Sylow p-groups are conjugates of each other. Furthermore we have that conjugation leaves the order of the element intact. For example let $P_1$ and $P_2$ be any Sylow p-groups. Then $exists g in G$ s.t. $gP_1g^-1 = P_2$. Also if $x$ is an element of $P_1$ of order $p$, then $gxg^-1$ is an element of $P_2$ of order $p$. In other word this means that each Sylow p-group have the same number of elements of order $p$.

Thus as we the number of Sylow p-subgroups is $1 pmod p$ the $n$ elements are partitioned into $kp+1$ Sylow p-subgroups, each containing the same number of elements.

For the second part you can use the notation used in the Sameer's answer and get that $n+1 equiv |S| equiv 0 pmod p$

share|cite|improve this answer

answered Jul 31 at 0:27

Stefan4024

27.8k52974

share|cite|improve this answer

share|cite|improve this answer

answered Jul 31 at 0:27

Stefan4024

27.8k52974

answered Jul 31 at 0:27

Stefan4024

27.8k52974

answered Jul 31 at 0:27

Stefan4024

27.8k52974

27.8k52974

add a comment | 

add a comment | 

up vote
1
down vote

While it is the case that the number of elements of order $p$ of a $p$-group is congruent to $-1$ modulo $p$, it is not true that the number of elements of order $p$ of a $p$-group must be of the form $p^k-1$ for some $kinmathbbZ_>0$. The solution you have is not entirely correct.

Here is a counterexample. Consider the dihedral group $$beginalignG&:=D_4=biglangle a,b,big|,a^4=1,,,,b^2=1,,text and bab^-1=a^-1bigrangle
\&=big,rin0,1,2,3text and sin0,1big,.endalign$$
Note that $|G|=8=2^3$. The elements of order $2$ of $G$ are listed below:
$$a^2,b,ab,a^2b,a^3b,.$$
That is, there are exactly $5$ elements of order $2$ in $G$. Clearly, $5equiv-1pmod2$, but it is not of the form $2^k-1$ for any $kinmathbbZ_>0$. The remaining $2$ non-identity elements of $G$ are $a$ and $a^3$, which are of order $4$.

---

Here is an alternative proof that the number $n$ of elements of order $p$ of a $p$-group $G$ satisfies $$nequiv -1pmodp,.$$ Consider the set $A$ of elements of $G$ containing all $xin G$ such that $x^p=1$. Clearly, $n=|A|-1$. We claim that $p$ divides $|A|$.

Let $Z$ denote the center of $G$. We note that the order of $Acap Z$ must be a power of $p$, being a subgroup of an abelian $p$-group $Ztrianglelefteq G$. Thus, $p$ divides $|Acap Z|$ (as every $p$-group has a nontrivial center, which contains an element of order $p$). It remains to verify that $p$ divides $|Asetminus Z|=|A|-|Acap Z|$.

We can partition $B:=Asetminus Z$ into orbits of elements of $B$ under conjugation in $G$. Clearly, any conjugate of an element of $B$ is in $B$. Due to the Orbit-Stabilizer Theorem, the size of each orbit is a power of $p$, and since the orbit contains a noncentral element, its size is larger than $1$. Consequently, every orbit of elements in $B$ is of size $p^k$ for some integer $kgeq 1$. This proves that $|B|$ is divisible by $p$. (In fact, $|B|$ is also divisible by $p-1$.)

---

As an example, with $G$ being the dihedral group $D_4$ as above, we have $A=(Acap Z)cup B$, where
$$Acap Z=Z=big1,a^4big
text and B=bigb,ab,a^2b,a^3bbig,.$$ The partition of $B$ into conjugacy orbits (or conjugacy classes) is
$$b,a^2bcupab,a^3b,.$$

share|cite|improve this answer

edited Jul 31 at 16:25

answered Jul 31 at 6:28

Batominovski

22.8k22776

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  I think we must write $|A setminus Z| = |A| - |Z cap A|$, as $Z$ need not sit wholly in $A$. (But the proof still goes through perfectly after this)
  – Sameer Kailasa
  Jul 31 at 16:20
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  OOppps, you are right. Sorry and thanks!
  – Batominovski
  Jul 31 at 16:22
  
  

  
  
  
  

add a comment | 

up vote
1
down vote

While it is the case that the number of elements of order $p$ of a $p$-group is congruent to $-1$ modulo $p$, it is not true that the number of elements of order $p$ of a $p$-group must be of the form $p^k-1$ for some $kinmathbbZ_>0$. The solution you have is not entirely correct.

Here is a counterexample. Consider the dihedral group $$beginalignG&:=D_4=biglangle a,b,big|,a^4=1,,,,b^2=1,,text and bab^-1=a^-1bigrangle
\&=big,rin0,1,2,3text and sin0,1big,.endalign$$
Note that $|G|=8=2^3$. The elements of order $2$ of $G$ are listed below:
$$a^2,b,ab,a^2b,a^3b,.$$
That is, there are exactly $5$ elements of order $2$ in $G$. Clearly, $5equiv-1pmod2$, but it is not of the form $2^k-1$ for any $kinmathbbZ_>0$. The remaining $2$ non-identity elements of $G$ are $a$ and $a^3$, which are of order $4$.

---

Here is an alternative proof that the number $n$ of elements of order $p$ of a $p$-group $G$ satisfies $$nequiv -1pmodp,.$$ Consider the set $A$ of elements of $G$ containing all $xin G$ such that $x^p=1$. Clearly, $n=|A|-1$. We claim that $p$ divides $|A|$.

Let $Z$ denote the center of $G$. We note that the order of $Acap Z$ must be a power of $p$, being a subgroup of an abelian $p$-group $Ztrianglelefteq G$. Thus, $p$ divides $|Acap Z|$ (as every $p$-group has a nontrivial center, which contains an element of order $p$). It remains to verify that $p$ divides $|Asetminus Z|=|A|-|Acap Z|$.

We can partition $B:=Asetminus Z$ into orbits of elements of $B$ under conjugation in $G$. Clearly, any conjugate of an element of $B$ is in $B$. Due to the Orbit-Stabilizer Theorem, the size of each orbit is a power of $p$, and since the orbit contains a noncentral element, its size is larger than $1$. Consequently, every orbit of elements in $B$ is of size $p^k$ for some integer $kgeq 1$. This proves that $|B|$ is divisible by $p$. (In fact, $|B|$ is also divisible by $p-1$.)

---

As an example, with $G$ being the dihedral group $D_4$ as above, we have $A=(Acap Z)cup B$, where
$$Acap Z=Z=big1,a^4big
text and B=bigb,ab,a^2b,a^3bbig,.$$ The partition of $B$ into conjugacy orbits (or conjugacy classes) is
$$b,a^2bcupab,a^3b,.$$

share|cite|improve this answer

edited Jul 31 at 16:25

answered Jul 31 at 6:28

Batominovski

22.8k22776

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  I think we must write $|A setminus Z| = |A| - |Z cap A|$, as $Z$ need not sit wholly in $A$. (But the proof still goes through perfectly after this)
  – Sameer Kailasa
  Jul 31 at 16:20
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  OOppps, you are right. Sorry and thanks!
  – Batominovski
  Jul 31 at 16:22
  
  

  
  
  
  

add a comment | 

up vote
1
down vote

up vote
1
down vote

While it is the case that the number of elements of order $p$ of a $p$-group is congruent to $-1$ modulo $p$, it is not true that the number of elements of order $p$ of a $p$-group must be of the form $p^k-1$ for some $kinmathbbZ_>0$. The solution you have is not entirely correct.

Here is a counterexample. Consider the dihedral group $$beginalignG&:=D_4=biglangle a,b,big|,a^4=1,,,,b^2=1,,text and bab^-1=a^-1bigrangle
\&=big,rin0,1,2,3text and sin0,1big,.endalign$$
Note that $|G|=8=2^3$. The elements of order $2$ of $G$ are listed below:
$$a^2,b,ab,a^2b,a^3b,.$$
That is, there are exactly $5$ elements of order $2$ in $G$. Clearly, $5equiv-1pmod2$, but it is not of the form $2^k-1$ for any $kinmathbbZ_>0$. The remaining $2$ non-identity elements of $G$ are $a$ and $a^3$, which are of order $4$.

---

Here is an alternative proof that the number $n$ of elements of order $p$ of a $p$-group $G$ satisfies $$nequiv -1pmodp,.$$ Consider the set $A$ of elements of $G$ containing all $xin G$ such that $x^p=1$. Clearly, $n=|A|-1$. We claim that $p$ divides $|A|$.

Let $Z$ denote the center of $G$. We note that the order of $Acap Z$ must be a power of $p$, being a subgroup of an abelian $p$-group $Ztrianglelefteq G$. Thus, $p$ divides $|Acap Z|$ (as every $p$-group has a nontrivial center, which contains an element of order $p$). It remains to verify that $p$ divides $|Asetminus Z|=|A|-|Acap Z|$.

We can partition $B:=Asetminus Z$ into orbits of elements of $B$ under conjugation in $G$. Clearly, any conjugate of an element of $B$ is in $B$. Due to the Orbit-Stabilizer Theorem, the size of each orbit is a power of $p$, and since the orbit contains a noncentral element, its size is larger than $1$. Consequently, every orbit of elements in $B$ is of size $p^k$ for some integer $kgeq 1$. This proves that $|B|$ is divisible by $p$. (In fact, $|B|$ is also divisible by $p-1$.)

---

As an example, with $G$ being the dihedral group $D_4$ as above, we have $A=(Acap Z)cup B$, where
$$Acap Z=Z=big1,a^4big
text and B=bigb,ab,a^2b,a^3bbig,.$$ The partition of $B$ into conjugacy orbits (or conjugacy classes) is
$$b,a^2bcupab,a^3b,.$$

share|cite|improve this answer

edited Jul 31 at 16:25

answered Jul 31 at 6:28

Batominovski

22.8k22776

While it is the case that the number of elements of order $p$ of a $p$-group is congruent to $-1$ modulo $p$, it is not true that the number of elements of order $p$ of a $p$-group must be of the form $p^k-1$ for some $kinmathbbZ_>0$. The solution you have is not entirely correct.

Here is a counterexample. Consider the dihedral group $$beginalignG&:=D_4=biglangle a,b,big|,a^4=1,,,,b^2=1,,text and bab^-1=a^-1bigrangle
\&=big,rin0,1,2,3text and sin0,1big,.endalign$$
Note that $|G|=8=2^3$. The elements of order $2$ of $G$ are listed below:
$$a^2,b,ab,a^2b,a^3b,.$$
That is, there are exactly $5$ elements of order $2$ in $G$. Clearly, $5equiv-1pmod2$, but it is not of the form $2^k-1$ for any $kinmathbbZ_>0$. The remaining $2$ non-identity elements of $G$ are $a$ and $a^3$, which are of order $4$.

---

Here is an alternative proof that the number $n$ of elements of order $p$ of a $p$-group $G$ satisfies $$nequiv -1pmodp,.$$ Consider the set $A$ of elements of $G$ containing all $xin G$ such that $x^p=1$. Clearly, $n=|A|-1$. We claim that $p$ divides $|A|$.

Let $Z$ denote the center of $G$. We note that the order of $Acap Z$ must be a power of $p$, being a subgroup of an abelian $p$-group $Ztrianglelefteq G$. Thus, $p$ divides $|Acap Z|$ (as every $p$-group has a nontrivial center, which contains an element of order $p$). It remains to verify that $p$ divides $|Asetminus Z|=|A|-|Acap Z|$.

We can partition $B:=Asetminus Z$ into orbits of elements of $B$ under conjugation in $G$. Clearly, any conjugate of an element of $B$ is in $B$. Due to the Orbit-Stabilizer Theorem, the size of each orbit is a power of $p$, and since the orbit contains a noncentral element, its size is larger than $1$. Consequently, every orbit of elements in $B$ is of size $p^k$ for some integer $kgeq 1$. This proves that $|B|$ is divisible by $p$. (In fact, $|B|$ is also divisible by $p-1$.)

---

As an example, with $G$ being the dihedral group $D_4$ as above, we have $A=(Acap Z)cup B$, where
$$Acap Z=Z=big1,a^4big
text and B=bigb,ab,a^2b,a^3bbig,.$$ The partition of $B$ into conjugacy orbits (or conjugacy classes) is
$$b,a^2bcupab,a^3b,.$$

share|cite|improve this answer

edited Jul 31 at 16:25

answered Jul 31 at 6:28

Batominovski

22.8k22776

share|cite|improve this answer

share|cite|improve this answer

edited Jul 31 at 16:25

edited Jul 31 at 16:25

edited Jul 31 at 16:25

answered Jul 31 at 6:28

Batominovski

22.8k22776

answered Jul 31 at 6:28

Batominovski

22.8k22776

answered Jul 31 at 6:28

Batominovski

22.8k22776

22.8k22776

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  I think we must write $|A setminus Z| = |A| - |Z cap A|$, as $Z$ need not sit wholly in $A$. (But the proof still goes through perfectly after this)
  – Sameer Kailasa
  Jul 31 at 16:20
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  OOppps, you are right. Sorry and thanks!
  – Batominovski
  Jul 31 at 16:22
  
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  I think we must write $|A setminus Z| = |A| - |Z cap A|$, as $Z$ need not sit wholly in $A$. (But the proof still goes through perfectly after this)
  – Sameer Kailasa
  Jul 31 at 16:20
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  OOppps, you are right. Sorry and thanks!
  – Batominovski
  Jul 31 at 16:22
  
  

  
  
  
  

1

1

I think we must write $|A setminus Z| = |A| - |Z cap A|$, as $Z$ need not sit wholly in $A$. (But the proof still goes through perfectly after this)
– Sameer Kailasa
Jul 31 at 16:20

I think we must write $|A setminus Z| = |A| - |Z cap A|$, as $Z$ need not sit wholly in $A$. (But the proof still goes through perfectly after this)
– Sameer Kailasa
Jul 31 at 16:20

OOppps, you are right. Sorry and thanks!
– Batominovski
Jul 31 at 16:22

OOppps, you are right. Sorry and thanks!
– Batominovski
Jul 31 at 16:22

add a comment | 

 

draft saved

draft discarded

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2867522%2fputnam-2007-a5-finite-group-n-elements-order-p-prove-either-n-0-or-p-d%23new-answer', 'question_page');

);

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Name Email

Name

Email

Name Email

Name

Email