OK that's cool, I thought that would be it although I'm really surprised you managed to compute

using that definition!

Consider the nth power of a prime,

, what numbers less than this share a factor with

?

Firstly what are the factors of

? Clearly just 1 and

. So any number less than

that share a factor must have p as a factor. Can you figure out how many such numbers there are? When you work this out, subtract this number from

and you will have the result for

(Effectively what you have done, is instead of working out how many numbers are coprime, you have worked out how many are not coprime, and subtracted this from p^n)

This will give you a quick generel result for

and you can just change the n to a three to give you your answer.

Good luck, and let us know where you get stuck.