In my response to the OP in Embedding $S_3$ into $Aut(F_2)$ (I continue notation from my response in that thread), I indicated the possibility that lifting elements from $GL_{2}(\mathbb{Z}/(p))$ to $Aut(B(2,p))$ could extend the ability of character-free methods in proving congruences relating the order of a group and its number of conjugacy classes. I can now report a small bit of concrete progress in this direction. Specifically, what I can prove is:

Theorem. If $G$ is a finite group of exponent 3, then $|G| \equiv c(G) \mod{16}$.

Proof. We regard the Burnside group $B(2,3) = < x,y|(*)^{3}=1 >$ (here $ * $ ranges over every word in the generators) as $< x,y>$ and specify elements of $Aut(B(2,3))$ by their action on $x$ and $y$. Specifically, consider the following elements of $Aut(B(2,3))$:

$\alpha: (x,y) \to (xy,x^{-1}y)$

$\beta: (x,y) \to (x,y^{-1})$

By checking that $\beta^{2} = 1$ and $\beta\alpha\beta = \alpha^{3}$, we see that $<\alpha,\beta>$ is a quotient of the semidihedral group of order $16$. By checking that $\alpha^{4}$ sends $(x,y)$ to $(x^{-1},xy^{-1}x^{-1})$ so that $\alpha^{4} \neq 1$, we see that $<\alpha,\beta>$ is semidihedral of order $16$.

Now let $<\alpha,\beta>$ act on non-commuting pairs of elements of our group $G$ of exponent 3. We wish to show that every non-identity element of $<\alpha,\beta>$ has no fixed points in its action on the set of non-commuting pairs of elements of $G$. Every non-identity element of $<\alpha,\beta>$ has a power equal to $\alpha^{4}$ or is conjugate to $\beta$, so it suffices to check this property for just $\alpha^{4}$ and $\beta$.

If $(x,y)$ is a fixed point of $\alpha$, then $x = x^{-1}$ so $x^{2} = 1$ and, since $x^{3} = 1$, $x = 1$ and $(x,y)$ is not a non-commuting pair.

If $(x,y)$ is a fixed point of $\beta$, then $y = y^{-1}$ so $y^{2} = 1$ and, since $y^{3} = 1$, $y = 1$ and $(x,y)$ is not a non-commuting pair.

Therefore every orbit for the action of $<\alpha,\beta>$ on the set of non-commuting pairs of elements of $G$ has exactly 16 elements and we conclude that 16 divides $|G|(|G| - c(G))$ . Since $|G|$ is odd, we conclude that $|G| \equiv c(G) \mod{16}$.

I do not know how to give a character-free proof of this congruence (either for general $p$-groups or just those of exponent $p$) for any prime $p$ with $p \equiv 3 \mod{4}$ and $p > 3$. Complicating hopes of extending this is the fact that $B(2,n)$ is not known to be finite for any larger odd value of $n$.

(i) I'm probably just not thinking clearly enough right now, but how does one use this to prove the congruence when $G$ is an arbitrary 3-group?

(ii) Is it hopeless to expect to extend this to larger primes congruent to 3 mod 4?