Are there any primes for which $a^2 = pb^2 + 1$ does not exist?

Question

The smallest solution to the above equation for various primes are:

$(p=2)$ $3^2 = 2*2^2 +1$

$(p=3)$ $2^2 = 2*1^2 +1$

$(p=5)$ $9^2 = 5*4^2 +1$

$(p=7)$ $8^2 = 7*3^2 +1$

Is there at least one solution for each prime? If there is one solution, there are infinite.

Answer 1

Here is the recipe for finding a (all the ) solution(s) of the equation $$a^2 - d b^2 = 1$$ where $d>0$ is a square free integer.

Consider the continued fraction expansion of $\sqrt{d}$. It will be of the form $$\sqrt{d} = [q,\overline{q_1, q_2 , \ldots q_r}]$$ with $q = [\sqrt{d}]$, with the sequence $q_1 q_2 \ldots q_r$ repeating indefinitely ( a (mixed) periodic continued fraction). Assume $r$ is minimal with this property. Then the minimal solution of the equation will be $(a_1,b_1)$, where $$\frac{a_1}{b_1} = [q,q_1, q_2 , \ldots q_{\epsilon r-1}] $$ where $\epsilon =1$ if $r$ even and $\epsilon=2$ otherwise. All the solutions will be $(a_k, b_k)$ where $$\frac{a_k}{b_k} = [q,q_1, q_2 , \ldots q_{k\epsilon r-1}]$$ Alternatively, $$(a_k + \sqrt{d} b_k ) = (a_1 + \sqrt{d} b_1)^k$$

Let's consider the example $d = 43= p_{14}$. We have the continued fraction expansion of $\sqrt{43}$: $$\sqrt{43} = [6,\overline{1,1,3,1,5,1,3,1,1,12}]$$ Calculate $$[6,1,1,3,1,5,1,3,1,1] = \frac{3482}{531}$$ Fair enough, we see that $$3482^2 - 43 \cdot 531^2 = 12\,124\,324 - 43 \cdot 281\,961 =12\,124\,324 - 12\,124\,323=1$$

But then also $$[6, 1, 1, 3, 1, 5, 1, 3, 1, 1, 12, 1, 1, 3, 1, 5, 1, 3, 1, 1, 12, 1, \ 1, 3, 1, 5, 1, 3, 1, 1] = \frac{168\,867\,574\,226}{25\,752\,063\,645}$$

and one can also check that $$168\,867\,574\,226^2 - 43\cdot 25\,752\,063\,645^2 =1$$

Of course, we have $$(3482 + \sqrt{43}\cdot 531)^3 = 168\,867\,574\,226 + \sqrt{43}\cdot25\,752\,063\,645$$

so the only surprise might be that all the solutions are coming from the continued fraction, which is true.

$\bf{Added:}$ Now that I looked at the example of @Travis, let's see whether the theory works:

$$\sqrt{61} = [7, \overline{1, 4, 3, 1, 2, 2, 1, 3, 4, 1, 14}]$$ The period $r =11$, odd, so we need to take chunks of lenght even multiple of $r$ $2kr$. The first one is $$\frac{a_1}{b_1} = [7, 1, 4, 3, 1, 2, 2, 1, 3, 4, 1, 14, 1, 4, 3, 1, 2, 2, 1, 3, 4, 1]=\frac{1766319049}{226153980}$$ confirmed.

Note that if we take the chunk of lenght $11$ instead $$\frac{a}{b} = [7, 1, 4, 3, 1, 2, 2, 1, 3, 4, 1] = \frac{29718}{3805}$$ we get $$29\,718- 61 \cdot 3\,805^2 = -1 $$

Answer 2

If one permits a general positive integer $n$ in place of the prime $p$, the resulting equation (in integers $x, y$) is called Pell's equation, and is usually rearranged to read $$x^2 - n y^2 = 1.$$ Lagrange showed that there are solutions for all nonsquare $n$, and so in particular it holds for all prime $n$. Note that even for modest $n$ the fundamental solution (i.e., the one minimizing positive $x$) can be large. For $n = 61$, for example, the fundamental solution is $(1\,766\,319\,049, 226\,153\,980)$.