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.

**Added on Feb 17, 2015:** Leonardo Zapponi has given now a complete answer to
the question in this note.

15more comments