The way I solved this problem was to use Wolfram Alpha: Plug in expressions of the form
Factor p^6 + 6
where p = 2, 3, 5, 7, 11, 13, 17, 19 and so on until you see a pattern. Then use what you know (perhaps Fermat's Little Theorem) to prove your guess. Others might be able to see the solution more quickly, but that's how I did it.