Given a positive integer $n$ which is not a perfect square, it is well-known that
[Pell's equation](http://en.wikipedia.org/wiki/Pell%27s_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](https://stefan-kohl.github.io/problems/pellpolynomials.txt).


**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](http://arxiv.org/pdf/1503.00637v1).



Parametric solutions of Pell's equation
Let $n$ be a positive integer which is not a square and consider a fundamental solution $(a,b)$ of Pell's equation
$$a^2-nb^2=1.$$
Setting
$$\begin{cases}
D=(a+1)^2b^2X^2+2(a+1)^2X+n,\\
P=b^4(a+1)X^2+2b^2(a+1)X+a,\\
Q=b^3X+b,
\end{cases}$$
we have the identity
$$P^2-DQ^2=1,$$
with $D(0)=n,P(0)=a$ and $Q(0)=b$. This explicitly answers the (first) question. A second post (below) shows that if $n$ is square-free and congruent to $3$ modulo $4$ then the degree of the polynomial $P$ is at most $2$.


In the rest of the post, we briefly sketch how the polynomials $P,Q$ and $D$ were constructed: let $P,Q,D\in\Bbb C[X]$ be three polynomials with
$$P^2-DQ^2=1$$
and $\deg(D)=2$. Here, we assume $\deg(P)=d>1$, so that $\deg(Q)=d-1$. Consider the polynomial $f=P^2$, so that $f'$ has degree $2d-1$. Setting $$P=u\prod\_{i=1}^r(X-x\_i)^{e\_i}\quad\mbox{and}\quad Q=v\prod\_{i=1}^s(X-y\_i)^{f\_i},$$
with $u,v\in\Bbb C,r\leq d$ and $s\leq d-1$, we obtain the factorization
$$f'=\prod\_{i=1}^r(X-x\_i)^{2e\_i-1}\prod\_{i=1}^r(X-y\_i)^{2f\_i-1}R,$$
with $R\in\Bbb C[X]$. Since $d=\sum\_{i=1}^re\_i=1+\sum\_{i=1}^sf\_i$, we find the identity
$$2d-1=\sum\_{i=1}^r(2e\_i-1)+\sum\_{i=1}^s(2f\_i-1)+\deg(R)=4d-2-r-s+\deg(R),$$
which leads to
$$r+s=2d-1+\deg(R).$$
It then follows that $r=d,s=d-1$ and $\deg(R)=0$, i.e. $P$ and $Q$ are separable. Remark that the polynomial $D$ is then itself separable. In this case, the cover $\Bbb P^1\to\Bbb P^1$ induced by $f$ is only ramified above $\infty,0$ and $1$, i.e. it is a Belyi map. The isomorphism classes of such covers are classified by Grothendieck's dessins d'enfants and, once we have fixed the integer $d$, there is a unique class with the above ramification data (totally ramified above $\infty$, all the points above $0$ have ramification index $2$ and the points above $1$ have ramification $2$ excepted two of them, which are unramified, corresponding to the roots of $D$). More precisely, if $T\_d\in\Bbb Z[X]$ denotes the Chebyshev polynomial (of the first kind) of degree $d$, there exist constants $\lambda\in\Bbb C^\times$ and $\nu\in\Bbb C$, such that
$$f=\frac{T\_{2d}(\lambda X+\nu)+1}2=T\_d(\lambda X+\nu)^2.$$
This shows how to construct $P$. For example, in individ's answer, we find
$$P=T\_2(\lambda X+\nu),$$
with $\lambda=\frac{\sqrt{2}}2$ and $\nu=\sqrt{2}$, while $\lambda=169i$ and $\nu=-99i$ (with $i^2=-1$) leads to Will Jagy's example for $n=29$.


We can then try to find a solution for general $n$ from the case $d=2$ in the above discussion. Consider a fundamental solution $(a,b)$ of the Pell's equation $a^2-nb^2=1$. It is clear that in Stefan Kohl's question, we can reduce to the case $k=0$.We have the identity $T\_2=2X^2-1$ and we therefore set
$$P=2(\lambda X+\nu)^2-1.$$
The condition $P(0)=a$ leads to the relation $\nu=\frac12\sqrt{2a+2}$, while $P\in\Bbb Z[X]$ gives the identity $P=NX^2+MX+a$, with $N$ and $M$ integers such that $4(a+1)N=M^2$. We then find the factorization
$$P^2-1=\left(\frac14M^2X^2+M(a+1)X+nb^2\right)\left(\frac M{2(a+1)}X+1\right)^2.$$
Finally, setting $M=2(a+1)b^2$, we can factor $b^2$ on the first factor of the above identity and put it in the second factor, which leads to the result.


**Added on Feb 17, 2015:** A complete answer to the question can be found in [this note](http://arxiv.org/abs/1503.00637).


