Surprising but simple group theory result on conjugacy classes I have read that for any group $G$ of order $2m+1$ (odd) with $n$ conjugacy classes, it is always the case that $16$ divides the value $(2m+1)-n = |G|-n$. 
This seems to me like an astonishing result: what on earth would $16$ have to do with every single odd group and its conjugacy classes? At any rate, I am wondering, assuming it is true, how would you go about proving it? I would like to show it in a reasonably simple way, but nothing whatsoever comes to mind, could anyone help? Many thanks - M.
 A: The number of conjugacy classes is the same as the number of irreducible representations; if $d_i$ is the set of dimensions of the irreducible representations, we know that $d_i | |G|$, hence $d_i$ is odd, and $|G| = \sum d_i^2$. Since $d_i$ is odd, we compute that $d_i^2 \equiv 1, 9 \bmod 16$, so it already follows that $|G| \equiv n \bmod 8$. To get the result $\bmod 16$ it suffices to show that the representations such that $d_i^2 \equiv 9 \bmod 16$ occur an even number of times.
In fact, we claim that no non-trivial irrep is self-dual, from which the above follows (since we can take the dual of an irrep with $d_i^2 \equiv 9 \bmod 16$ to get another one). This is equivalent to the claim that no non-identity element is conjugate to its inverse, which follows from the fact that no element of $G$ can act by a permutation of order two. 
A: This classic theorem of Burnside is often presentated as an example of a theorem that is difficult to prove without using representation theory. However, one can in fact provide elementary proofs for results of this sort. For example, see Reid: The number of conjugacy classes, AMM, 1998, 359-361, where, generalizing results in an earlier 1995 AMM paper by Poonen),  if $G$ is a finite group such that every prime divisor $p$ of its order satisfies $p \equiv 1\ (mod\ m)\:,\:$ he proves the strongest possible congruence between $|G|$ and $n$. Below is the Zbl review by R. W. van der Waall (Amsterdam) followed by Burnside's original proof, from S.222, p.294 of Theory of groups of finite order, 1911.

Let $\cal G$ stand in general for a finite group; $p$ for a prime number.
    Let $m\in\mathbb Z_{\geq 1}$. Consider $${\cal G}_m=\{{\cal G}\ :\  p\mid|{\cal
G}|\ \Rightarrow\ p\equiv 1\ (mod\ m)\}.$$ Let $B(m)$ be the greatest common
    divisor of all numbers $|{\cal G}|-s$, where $\cal G$ runs through ${\cal
G}_m$. Here $s$ stands for the number of conjugacy classes of $\cal G$.  
In this paper the following is proved. Theorem. If $m >2$, then $B(m)$ is the
    least common multiple of $48$ and $2m^2$. $\:$ Also $B(2)=16$ and $B(1)=1$.  
The  proof is elementary, without using representation theory. It uses the facts
    that each of $3, 16$ and $2m^2$ divides $B(m)$. The case $3\mid B(m)$ is
    proved here by elementary means; the case $2m^2\mid B(m)$ likewise as done
    by B. Poonen [in Am. Math. Mon. 102, No. 5, 440-442 (1995; Zbl
    0828.11002)]. The fact $16\mid B(m)$ follows for $m >2$ from $B(2)\mid B(m)$,
    whereas Burnside proved that $16\mid B(2)$ (before 1911).  
Reviewer's  remark: Using representation theory, Burnside proved that if $|\cal G|$ is
    odd, then $|\cal G|\equiv s\pmod{16}$. Does there exist an elementary proof,
    i.e. without using representation theory and without using the Feit-Thompson
    theorem on the solvability of finite groups of odd order? A result by K. A.
    Hirsch in that direction seems to be unjustified.



