Again posted before : http://www.artofproblemsolving.com/Forum/viewtopic.php?f=57&t=552603&p=3209056#p3209056

I think Vieta Jumping can kill this.

I don't see how ... It is more related to Pell equations.

It is hard Pell Equation , first person on number theory exam just get 14 from 25 on this question.

We will use the usual notation $N(x+y\sqrt{p})=x^2-py^2$. It is easy to see that $N(ab)=N(a)N(b)$, for $a,b \in \mathbb{Z} [\sqrt{p}]$ Let's first find the minimal solution to $N(x+y\sqrt{p})=1$ ($x,y$ positive). $x^2-py^2=1$ factors as $py^2=(x-1)(x+1)$. $x-1=p$ or $x+1=p$ gives no solution, and $x+1=2p$ gives the first solution $(x,y)=(2n^2+1,2n)$. So $\alpha=(2n^2+1)+2n\sqrt{p}$ is the minimal solution to $N(x+y\sqrt{p})=1$. Now notice that for any solution $\beta$ for $ N(\beta)=n^2$, $\beta \alpha^k$ and $\beta \alpha^{-k}$ are also solutions (notice that $\alpha^{-1}=(2n^2+1)-2n\sqrt{p} a,b \in \mathbb{Z} [\sqrt{p}]$). So for each solution to $N(\beta)=n^2$ we get a family of solutions. It is clear that in each family of solutions there is exactly one solution satisfying $1<\beta \le \alpha$. So it is enough to check such solutions. Let $\beta = x+y\sqrt{p}$. We know $\beta=x+y\sqrt{p}=\frac{n^2}{x-y\sqrt{p}}\le \alpha \Rightarrow x-y\sqrt{p} \ge \frac{n^2}{\alpha}$ Summing up to $x+y\sqrt{p} \ge 1$, we get $x>\frac{n^2}{\alpha}+1>0$ Also,$x+y\sqrt{p}=\frac{n^2}{x-y\sqrt{p}}>1 \Rightarrow$ $x-y\sqrt{p}<n^2$, so $y\sqrt{p}>x-n^2$. But $x^2 \equiv n^2 \,(mod\,p)$. If $x=n$, we have the clear solution $\beta=n+0\sqrt{p}$. Otherwise, $x \ge p-n$, and then $y\sqrt{p}>1-n>-\sqrt{p} \Rightarrow y$ is nonnegative. So we have aways $x,y \ge 0$ for such solutions. (so this solution $\beta$ s.t. $1<\beta\le \alpha$ is actually the least non-negative solution of its family, because of course that in a solution that is less than $1$ either $x$ or $y$ is negative). Therefore, if we find all solutions $\beta$ such with $1<\beta \le \alpha$, ALL the solutions of our initial equation will be given by $\beta \alpha^k$, for nonegative $k$. Now lets finally find our solutions $\beta$. By using $1<\beta \le \alpha$ we get the bound: $\beta=x+y\sqrt{p}=\frac{n^2}{x-y\sqrt{p}}>1 \Rightarrow x-y\sqrt{p}<n^2$. Summing up to $x+y\sqrt{p}\le 2n^2+1+2n\sqrt{p}$ we get $2x<3n^2+1+2n\sqrt{p}<5n^2+2 \Rightarrow x<\frac{5n^2}{2}+1$ Factoring the initial equation: $py^2=(x-n)(x+n)$ If $y=0$ we have the solution $(n,0)$ we had already found. Otherwise, we have $p|x-n$ or $p|x+n$ If $p|x-n$ we have $x=p+n$ or $x=2p+n$ ($x$ can't be greater, because $x<\frac{5n^2}{2}+1$) $x=p+n$ gives the solution $(x,y)=(n^2+n+1,n+1)$ and $x=2p+n$ gives no solution. If $p|x+n$ we have $x=p-n$ or $x=2p-n$ $x=p-n$ gives the solution $(x,y)=(n^2-n+1,n-1)$ and $x=2p-n$ gives no solution. Finally, we conclude that all the non-negative solutions are given by: $x+y\sqrt{p}=n(2n^2+1+2n\sqrt{p})^k$ $x+y\sqrt{p}=(n^2+n+1+(n+1)\sqrt{p})(2n^2+1+2n\sqrt{p})^k$ or $x+y\sqrt{p}=(n^2-n+1+(n-1)\sqrt{p})(2n^2+1+2n\sqrt{p})^k$ For some non-negative $k$.

rsa365 wrote: It is clear that in each family of solutions there is exactly one solution satisfying $1<\beta \le \alpha$. . can anybody explain this part?

can someone explain why k has to be nonnegative?

I don't think we need to assume $p$ is prime in this problem to have a solution. The full solution set of solutions of the Diophantine equation is as follows: First of all pick any $n\in\mathbb{Z}$. Then $(x,y)$ pairs of positive integers are \[x=\frac{n}{2}\left(\left(2n^2+1+2n\sqrt{n^2+1}\right)^k+\left(2n^2+1-2n\sqrt{n^2+1}\right)^k\right)\]\[y=\frac{n}{2\sqrt{n^2+1}}\left(\left(2n^2+1+2n\sqrt{n^2+1}\right)^k-\left(2n^2+1-2n\sqrt{n^2+1}\right)^k\right)\] for all $k\in\mathbb{N}$ For any other solution in the non-zero integers, just reflect the above solution set about the $x$-axis, $y$-axis, or both. Finally there are the two solutions $(\pm n,0)$.