Quisiera hacer un par de observaciones. En la discusión general del problema que haces, no hay ningún indicio que excluya de forma explícita a los casos n = 1, 2, 4. ¡¡¡ pero funcionan!!!
Esto es una señal de que "algo debe fallar".
Veamos. En tu propuesta, el punto de partida es tomar p = 1+nn y hacer dos supuestos:
Que p divida a n y que p no divida a n.
Pero p nunca puede dividir a n, ya que p=1+nn > n para todo n natural. (Mayor estricto).
En el otro caso, llegas a la conclusión de que nn es congruente con p-1 módulo p. Pero no es que sea congruente, es que es exactamente p-1. Por tanto en la expresión
n^n = p*q + (p-1)
se tiene que q = 0 y no hay contradicción alguna.
El problema está en tratar a "p" como un primo cualquiera y menor que 1+nn y al mismo tiempo como p = 1+nn.
Espero que se entienda.
Un saludo