Return to Answer

To state the obvious: Such an $n$ must naturally have $p\equiv 1 \pmod{12}$ and $q\equiv 1\pmod{4}$.

Also, it seems that, for each $q$ a prime such that $q^2\vert (1 + p^2), 1 + q^2 + q^4\equiv \epsilon\pmod{p}$, where $p\equiv \epsilon\pmod{4}$ (this holds with or without the $p\equiv 1\pmod{4}$ condition, of course). In this case, we have that $\lceil \sqrt{p}\rceil\leq q< p$.

EDIT: Typos galore!

To state the obvious: Such an $n$ must naturally have $p\equiv 1 \pmod{12}$ and $q\equiv 1\pmod{4}$. The first condition is implied by the fact that $1 + q^2 + q^4 = 0\pmod{p}$, and so, since $p\neq 3$, $q^6\equiv 1\pmod{p}$ giving that $3\vert p-1$, or $p\equiv 1\pmod{3}$. The second is given by the fact that $1+p^2\equiv 0\pmod{q}$ gives that $p^2\equiv -1\pmod{q}$, and so $q\equiv 1\pmod{4}$, since $\left(\frac{-1}{q}\right) = 1$.

EDIT: Typos galore!

EDIT 2: I undeleted.

To state the obvious: Such an $n$ must naturally have $p\equiv 1 \pmod{12}$ and $q\equiv 1\pmod{4}$.

Also, it seems that, for each $q$ a prime such that $q^2\vert (1 + p^2), 1 + q^2 + q^4\equiv \epsilon\pmod{p}$, where $p\equiv \epsilon\pmod{4}$ (this holds with or without the $p\equiv 1\pmod{4}$ condition, of course). In this case, we have that $\lceil \sqrt{p}\rceil\leq q\leq p$.

EDIT: Typos galore!

To state the obvious: Such an $n$ must naturally have $p\equiv 1 \pmod{12}$ and $q\equiv 1\pmod{4}$.

Also, it seems that, for each $q$ a prime such that $q^2\vert (1 + p^2), 1 + q^2 + q^4\equiv \epsilon\pmod{p}$, where $p\equiv \epsilon\pmod{4}$ (this holds with or without the $p\equiv 1\pmod{4}$ condition, of course). In this case, we have that $\lceil \sqrt{p}\rceil\leq q< p$.

EDIT: Typos galore!

To state the obvious: Such an $n$ must naturally have $p\equiv 1 \pmod{12}$ and $q\equiv 1\pmod{4}$.

Also, it seems that, for each $q$ a prime such that $q^2\vert (1 + p^2), 1 + q^2 + q^4\equiv \epsilon\pmod{p}$, where $p\equiv \epsilon\pmod{4}$ (this holds with or without the $p\equiv 1\pmod{4}$ condition, of course). In that case, though, we see that $q\equiv -1\pmod{p}$, since $p\neq 3$. Thus, we see that $p\leq q+1$. $p^2 + 1\equiv 0\pmod{q^2}$ gives $q^2\leq 1+p^2$. Since $p\neq q$ and both $q+1$ and $q-1$ are even, we see that, first, $p\leq q-2$, so $p^2\leq q^2 - 4q + 4$. Hence, $1+p^2\leq 5-4q + q^2$. Coupled with the second inequality, we see that $q\leq \frac{5}{4}$, which is impossible.

Of course, proving that the first claim is the case is the hard part...--if it's even true. (Note: I would have commented this all, but I can't for some reason--sorry!)

EDIT: Typos galore!

To state the obvious: Such an $n$ must naturally have $p\equiv 1 \pmod{12}$ and $q\equiv 1\pmod{4}$.

Also, it seems that, for each $q$ a prime such that $q^2\vert (1 + p^2), 1 + q^2 + q^4\equiv \epsilon\pmod{p}$, where $p\equiv \epsilon\pmod{4}$ (this holds with or without the $p\equiv 1\pmod{4}$ condition, of course). In this case, we have that $\lceil \sqrt{p}\rceil\leq q\leq p$.

EDIT: Typos galore!