A user on MSE, @martin , asked <https://math.stackexchange.com/questions/1611411/pell-equations-upper-bound> about an upper bound for $x$ in $x^2 - p y^2 = 1,$ when $p$ is prime. I checked, it appears reasonable to guess that
$$ x < p^{\sqrt p} $$
when $p > 2.$ I had the computer solve by Lagrange's method, no continued fractions, no decimal accuracy required, no memory required, but the method is still elementary. I had the machine print out whenever $\log\_p(\log\_p(x))$ increased. It was necessary to take $p > 2$ because $x=3$ gives an overly large logarithm. Meanwhile, if all we do is print whenever $x$ itself increases, there are several composite numbers below $100$ that get included, after that they give way to primes $p \equiv 1 \pmod 4.$ I put in a fair amount of effort but was unable to draw any firm conclusions.


So, the questions would be, (I) what is unconditionally proved about the size of $x,$ (II) what is proved under conjectures that people mostly believe true, (III) what are the most optimistic things conjectured? 



```
p                                       
5        log_p(x)     1.365212388971971   log_p(log_p(x)) 0.1934277864616169   X 9  
13       log_p(x)     2.524585016802303   log_p(log_p(x)) 0.3610506760085375   X 649  
61        log_p(x)    5.17947382679923   log_p(log_p(x))  0.4000860954668999   X 1766319049  
109      log_p(x)     6.969012778576543   log_p(log_p(x)) 0.4138413148682316   X 158070671986249  
421      log_p(x)    12.79922341582056   log_p(log_p(x))  0.4218996203501611   X 3879474045914926879468217167061449  
1621     log_p(x)    23.61505725662223   log_p(log_p(x))  0.4278136548619654   X 6298101812493732343034974500091457815529942308667051412857352310169665125001  
.....................
44450701  log_p(x) 2641.408511213517     log_p(log_p(x))  0.4474228404332914   X  is rather large...

```

Why not, here is how it begins if we print every time $x$ increases and make no requirement about loglog, allowing $n$ composite in $x^2 - n y^2$ with $2 \leq n \leq 500$



```
2  log_p(x) 1.584962500721156   log_p(log_p(x))   0.6644487074538893   X 3
5  log_p(x) 1.365212388971971   log_p(log_p(x))   0.1934277864616169   X 9
10  log_p(x) 1.278753600952829   log_p(log_p(x))  0.1067868696893203   X 19
13  log_p(x) 2.524585016802303   log_p(log_p(x))  0.3610506760085375   X 649
29  log_p(x) 2.729264122987999   log_p(log_p(x))  0.298171610554983   X 9801
46  log_p(x) 2.637925539730376   log_p(log_p(x))  0.2533517055829028   X 24335
53  log_p(x) 2.79606031271967   log_p(log_p(x))   0.258976271165875   X 66249
61  log_p(x) 5.17947382679923   log_p(log_p(x))   0.4000860954668999   X 1766319049
109  log_p(x) 6.969012778576543   log_p(log_p(x)) 0.4138413148682316   X 158070671986249
181  log_p(x) 8.146702019142648   log_p(log_p(x)) 0.4035037766708247   X 2469645423824185801
277  log_p(x) 8.271023203635528   log_p(log_p(x)) 0.3756670785256742   X 159150073798980475849
397  log_p(x) 8.05129073299257   log_p(log_p(x))  0.3485719633766078   X 838721786045180184649
409  log_p(x) 8.576275777667302   log_p(log_p(x)) 0.3573497754649824   X 25052977273092427986049
421  log_p(x) 12.79922341582056   log_p(log_p(x)) 0.4218996203501611   X 3879474045914926879468217167061449

```


Upper bound on answer for Pell equation
Let $d$ be a positive fundamental discriminant, $\epsilon\_d$ denote the fundamental unit, $h(d)$ the class number, and $\chi\_d$ the primitive character associated to the discriminant $d$. The class number formula gives 
$$ 
\log \epsilon\_d = \sqrt{d} L(1,\chi\_d)/h(d) \le \sqrt{d} L(1,\chi\_d), 
$$ 
since the class number $h(d) \ge 1$. Now it is known that 
$L(1,\chi\_d) \le C \log d$ for a constant $C$. This upper bound is completely effective. The best known constant $C$ is (for large enough $d$) 
$$ 
\frac{1}{4} \Big(2-\frac{2}{\sqrt{e}} \Big). 
$$
If we knew something about how small primes split in ${\Bbb Q}(\sqrt{d})$ then this could be improved by taking those Euler factors into account (for example, we can use this if $d$ is even which would happen for primes $p\equiv 3\pmod 4$ in the question). This is a result of P.J. Stephens and uses the Burgess bound for character sums (together with an argument from multiplicative number theory along the lines of Vinogradov's $1/\sqrt{e}$ argument for the least quadratic non-residue). For a discussion of Stephens's result and extensions, see [Granville and Soundararajan](http://arxiv.org/pdf/math/0106176v1.pdf).  

This would be enough to give your conjecture of $p^{C\sqrt{p}}$ (one needs a little care to go from the fundamental unit to the solution to Pell's equation -- i.e. one might need to take a small power of the fundamental unit). Also see this paper of [Hua](https://projecteuclid.org/download/pdf_1/euclid.bams/1183504769) which explicitly states a bound along the lines you want, tracing it back to Schur. Finally, [Louboutin](http://ac.els-cdn.com/S0022314X00925459/1-s2.0-S0022314X00925459-main.pdf?_tid=3fa63064-c560-11e5-be6f-00000aacb361&acdnat=1453945468_f71b19db20f8e005582a1ceb329ef164) has looked at explicit upper bounds for $L(1,\chi)$ (see Theorem 5.1 there). 


The above results are unconditional. On GRH one can do a bit better, since $L(1,\chi\_d)$ may then be bounded by $C\log \log d$, and then one would get a better bound of $(\log p)^{C\sqrt{p}}$ in your problem (see [Theorem 1.5 of this paper](http://arxiv.org/pdf/1309.3595v1.pdf) for an explicit GRH bound), and I think that can probably happen (although this is not clear since we don't know that the class number can get down to $1$). [Jacobson, Lukes and Williams](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.37.7045&rep=rep1&type=pdf) report on extensive calculations on regulators, and at the end of the paper state the belief that the fundamental unit can get as large as $\exp(c \sqrt{d}\log \log d)$; however, as also noted there, unconditionally we only know that the fundamental unit (or the solution in Pell's equation) sometimes gets as large as $\exp(c(\log d)^4)$ -- so there is a very large gap in our understanding. (See also my answer to the related MO question [Upper bound for class number of a real quadratic field](https://mathoverflow.net/questions/144024/upper-bound-for-class-number-of-a-real-quadratic-field/144026#144026) .)


