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.

Not sure degree 6 is necessary. See what you can do with $$ n=29, \; k=1, \; D = 169 x^2 - 198 x + 58, $$ $$ n=53, \; k=1, \; D = 625 x^2 - 886 x + 314, $$

The coefficient of $x^2$ seems to be $w^2,$ where $v^2 - n w^2 = -1.$ Such a $w$ is guaranteed to exist when $n \equiv 1 \pmod 4$ is prime.

Ummm; the discriminants of the quadratic forms $169 x^2 - 198 xy + 58y^2$ and $625 x^2 - 886 xy + 314y^2$ are $-4.$ Same for $25 x^2 \pm 14 xy + 2 y^2$ and $x^2 + y^2,$ also the ones for primes $73,89,113,$ also cases where you found $P$ quadratic and $Q$ linear.

LATER: $29$ worked very well. $$ n=29, \; k=1, \; D = 169 x^2 - 198 x + 58, $$ $$ P = 57122 x^2 - 66924 x + 19603, $$ $$ Q = 4394 x - 2574, $$ $$ P^2 - D Q^2 = 1, $$ $$ P(1) = 9801, \; Q(1) = 1820, \; D(1) = 29. $$

Here are some results concerning the degree of the polynomial $P$. We only treat the cases where $n$ is a positive, square-free integer congruent to $3$ modulo $4$, showing that the degree of $P$ is less than or equal to $2$.

We start by the weaker assumption that, given the positive integer $n$ and a solution $(a,b)$ of Pell's equation $a^2-nb^2=1$, there exist polynomials $D,P,Q\in\Bbb Q[X]$ and a rational number $k$ such that $P^2-DQ^2=1$, with $D(k)=n,P(k)=a$ and $Q(k)=b$. Let $d$ be the degree of $P$. As mentioned in my other post, and following the conventions and results in David Speyer's answer, there exist constants $\alpha\in\Bbb C$ and $\beta,\gamma\in\Bbb Q$, with $\alpha^2,\gamma^2\in\Bbb Q$ such that $$\begin{cases} P=\pm T_d\left(\alpha(X+\beta)\right),\\ Q=\gamma U_{d-1}\left(\alpha(X+\beta)\right),\\ D=\gamma^{-2}\left(\alpha^2(X+\beta)^2-1\right), \end{cases}$$ where $T_d$ (resp. $U_d$) denotes the degree $d$ Chebyshev polynomial of the first kind (resp. of the second kind). From the hypothesis on $P$, we can assume $\beta=0$. We have the identity $$T_d+U_{d-1}\sqrt{X^2-1}=\left(X+\sqrt{X^2-1}\right)^d,$$ which leads to $$P+Q\sqrt{D}=\left(\alpha X+\sqrt{\alpha^2X^2-1}\right)^d.$$ If $d$ is odd then the explicit expression of $T_d$ shows that $\alpha$ (and therefore $\gamma$) is rational. Evaluating at $k$, we then obtain the identity $$a+b\sqrt{n}=\left(u+v\sqrt{n}\right)^d,$$ with $u,v\in\Bbb Q$. It then follows that $u+v\sqrt{n}$ is a unit in the ring of integers of $\Bbb Q(\sqrt{n})$ and, since we are assuming $n\equiv3\pmod4$, the elements $u$ and $v$ are integers. In particular, for $d>1$, the couple $(a,b)$ cannot be a fundamental solution of Pell's equation.

From now on, we assume $d=2m$ even. For $\alpha\in\Bbb Q$, we proceed as above and deduce that $(a,b)$ cannot be a fundamental solution for $d>1$. Suppose then that $\alpha=\sqrt{w}$, we $w\in\Bbb Q$ not a square, so that $\gamma=t\alpha$, with $t\in\Bbb Q$. We have the relation $$T_d+U_{d-1}\sqrt{X^2-1}=\left(X^2-1+2X\sqrt{X^2-1}\right)^m$$ and thus $$P+Q\sqrt{D}=\left(\alpha^2X^2-1+2\alpha\sqrt{\alpha^2X^2-1}\right)^m.$$ Evaluating at $k$, we then easily obtain the identity $$a+b\sqrt{n}=\left(u+v\sqrt{n}\right)^m,$$ with $u,v\in\Bbb Q$. Once again, for $m>1$, it then follows that the couple $(a,b)$ cannot be a fundamental solution, leading to the result.

A final remark: for general $n$, if $(a,b)$ is a fundamental solution then $$a+b\sqrt{n}=\left(u+v\sqrt{n}\right)^r,$$ where $u+v\sqrt{n}$ is a fundamental unit of $\Bbb Q(\sqrt{n})$. For example, in Stefan Kohl's example for $n=13$, we have $$649+180\sqrt{13}=\left(\frac{11}2+\frac32\sqrt{13}\right)^3.$$ I'm definitely not an expert on this subject, but the above discussion combined with an explicit bound for the integer $r$ would lead to a bound for the degree of $P$ and therefore give a complete answer to the second question.