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

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

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 $\mathbb{Z}/p\mathbb{Z}$ acts on $S$ by cyclic rotations. Thus, we have $$|S| = \#\{\text{orbits of size 1}\} + \#\{\text{orbits of size p}\} \cdot p$$ Orbits of size 1 correspond to tuples of the form $(x, x, x, \cdots, x)$, i.e. elements $x\in G$ of order $p$, excepting the orbit corresponding to the trivial tuple $(1, 1, 1, \cdots 1)$. Thus, $$\#\{\text{orbits of size 1}\} = \#\{\text{elements 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.

• 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 '18 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 '18 at 0:31
• One for The Book. Beautiful proof! – Mike Jul 31 '18 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 '18 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 '18 at 0:54

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$

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 $k\in\mathbb{Z}_{>0}$. The solution you have is not entirely correct.

Here is a counterexample. Consider the dihedral group \begin{align}G&:=D_4=\big\langle a,b\,\big|\,a^4=1\,,\,\,b^2=1\,,\text{ and }bab^{-1}=a^{-1}\big\rangle \\&=\big\{a^r\,b^s\,\big|\,r\in\{0,1,2,3\}\text{ and }s\in\{0,1\}\big\}\,.\end{align} 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, $5\equiv-1\pmod{2}$, but it is not of the form $2^k-1$ for any $k\in\mathbb{Z}_{>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 $$n\equiv -1\pmod{p}\,.$$ Consider the set $A$ of elements of $G$ containing all $x\in 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 $A\cap Z$ must be a power of $p$, being a subgroup of an abelian $p$-group $Z\trianglelefteq G$. Thus, $p$ divides $|A\cap Z|$ (as every $p$-group has a nontrivial center, which contains an element of order $p$). It remains to verify that $p$ divides $|A\setminus Z|=|A|-|A\cap Z|$.

We can partition $B:=A\setminus 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 $k\geq 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=(A\cap Z)\cup B$, where $$A\cap Z=Z=\big\{1,a^4\big\} \text{ and }B=\big\{b,ab,a^2b,a^3b\big\}\,.$$ The partition of $B$ into conjugacy orbits (or conjugacy classes) is $$\{b,a^2b\}\cup\{ab,a^3b\}\,.$$

• 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 '18 at 16:20
• OOppps, you are right. Sorry and thanks! – Batominovski Jul 31 '18 at 16:22