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
 A: 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.
A: 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$
A: 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\}\,.$$
