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

> <b>Question:</b> 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$?

<b>Example:</b> 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][2].

  [1]: http://en.wikipedia.org/wiki/Pell%27s_equation
  [2]: http://www.gap-system.org/DevelopersPages/StefanKohl/problems/pellpolynomials.txt