obvious, we have $gcd(n, q) = gcd(n+1, q) = 1$. by the fermat little theorem, we have $q| (n+1)^{q-1} - n^{q-1}$. so, $q| gcd ((n+1)^p - n^p, (n+1)^{q-1} - n^{q-1}) = (n+1)^{gcd(p,q-1)} - n^{gcd(p,q-1)}$. if $q-1$ isn´t divisible by $p, q|1$, contradiction. so, $p|q-1$.

is $q$ prime ?

i prove that all prime divisors of $(n+1)^p - n^p$ are in the form $pk+1$, so, all divisors are in this form.

Arne wrote: Let $n$ be a positive integer, let $p$ be prime and let $q$ be a divisor of $(n + 1)^p - n^p$. Show that $p$ divides $q - 1$. Obviously $q \nmid n$. So $(n+1)^{p} - n^p \equiv 0 \bmod q$ only if $(1 + n^{-1})^p \equiv 1 \bmod q$. Hence $p = \mbox{ord}_q(1 + n^{-1})$, and subsequently $p \mid (q-1)$, if $q \in \mathfrak{P}$. Moreover, if $q \not \in \mathfrak{P}$, however it has to be a product of primes $\equiv 1 \bmod p$, which implies $q \equiv 1 \bmod p$. The claim follows!

Simple problem, isn't it, but only very few teams solved it (Poland, St Petersburg and Germany, I believe).

Arne which is your solution ?

It's very similar to the one hitlEULER gave. I must say that the solution by e.lopes is a bit more elegant