Given a positive integer $n$ which is not a perfect square, it is well-known that Pell's equation $a^2 - nb^2 = 1$ is always solvable in non-zero integers $a$ and $b$.

Question: Let $n$ be a positive integer which is not a perfect square. Is there always a polynomial $D \in \mathbb{Z}[x]$ of degree $2$, an integer $k$ and nonzero polynomials $P, Q \in \mathbb{Z}[x]$ such that $D(k) = n$ and $P^2 - DQ^2 = 1$, where $a = P(k)$, $b = Q(k)$ is the fundamental solution of the equation $a^2 - nb^2 = 1$?

If yes, is there an upper bound on the degree of the polynomials $P$ and $Q$ -- and if so, is it even true that the degree of $P$ is always $\leq 6$?

Example: Consider $n := 13$. Putting $D_1 := 4x^2+4x+5$ and $D_2 := 25x^2-14x+2$, we have $D_1(1) = D_2(1) = 13$. Now the fundamental solutions of the equations $P_1^2 - D_1Q_1^2 = 1$ and $P_2^2 - D_2Q_2^2 = 1$ are given by

• $P_1 := 32x^6+96x^5+168x^4+176x^3+120x^2+48x+9$,

• $Q_1 := 16x^5+40x^4+56x^3+44x^2+20x+4$

and

• $P_2 := 1250x^2-700x+99$,

• $Q_2 := 250x-70$,

respectively. Therefore $n = 13$ belongs to at least $2$ different series whose solutions have ${\rm deg}(P) = 6$ and ${\rm deg}(P) = 2$, respectively.

Examples for all non-square $n \leq 150$ can be found here.

Added on Feb 3, 2015: All what remains to be done in order to turn Leonardo's answers into a complete answer to the question is to find out which values the index of the group of units of $\mathbb{Z}[\sqrt{n}]$ in the group of units of the ring of integers of the quadratic field $\mathbb{Q}(\sqrt{n})$ can take. This part is presumably not even really MO level, but it's just not my field -- maybe someone knows the answer?

Added on Feb 14, 2015: As nobody has completed the answer so far, it seems this may be less easy than I thought on a first glance.