The divisors of $p-1$ and high-degree residues modulo $p$

Here is a somewhat more explicit version of a question that I asked a while ago.

Suppose that $p$ is a prime of the form $p=2n(n+1)+1$, with a positive integer $n$. Can every odd prime divisor of $p-1$ be a residue of degree $2(n+1)$ modulo $p$? That is, can one have $q^n\equiv 1\pmod p$ for every odd prime $q\mid p-1$?

Heuristically, this is extremely unlikely, and a computer search yields no such primes in the range $1<n\le10^7$ (the case $n=1$ being a trivial exception). However, I got stuck trying to prove anything rigorously.

My guess is that this may be related to higher reciprocity laws, but at least the Eisenstein reciprocity does not seem to help.

• I agree that heuristically it's extremely unlikely. Do you have any reason to believe that a nice algebraic proof exists? – Greg Martin Dec 4 '14 at 7:48
• Greg: No such reasons - but I'd be equally happy with a not-so-nice proof! – Seva Dec 4 '14 at 7:50