I believe we can use the Burnside Basis Theorem here (see p140 of Robinson's book, `A Course in the Theory of Groups'). It actually yields quite a neat proof, which is why I post this...it is also one of my favourite theorems!

Now, because we are in a non-abelian group of order

we must have that

, by the BBT.

Also by the BBT we have that

.

Therefore, it is sufficient to prove that

, which it is (see topspin's post).

I am, however, a bit confused as to where we need odd primes. Certainly this proof does not rely on odd primes, glancing over at p141 of Robinson I see that the identity in the hint doesn't need odd primes either, and I'm pretty sure topspin's proof doesn't need odd primes...also, the result does hold for the Quaternion group, and for

, the two non-abelian groups of order 8...

EDIT: for notation,

the Frattini subgroup

.