Prime $p$ with $p^2=3m^2+1$ and $p\equiv 1 \mod 4$

The solutions of the Pell equation $u^2-3v^2=1$ with $u\equiv 1\pmod{4}$ are of the form $$u_k+v_k\sqrt{3}=\left(97+56\sqrt{3}\right)^k=\left(2+\sqrt{3}\right)^{4k}.\tag{1}$$

Turns out, $u_k$ is a divisor of $u_{km}$ when $m>1$ is odd. This is because $$u_{km}+v_{km}\sqrt{3}=(u_k+v_k\sqrt{3})^m.$$ and the terms of the binomial expansion of the right side which have an even number of $v_k\sqrt{3}$ in the product must have an odd number of factors of $u_k.$

So $u_k$ cannot be prime unless $k$ is a power of $2.$ So the only possible values of $p$ are of the form: $$u_{2^i}=\left\lceil\frac{1}{2}\left(2+\sqrt{3}\right)^{2^{i+2}}\right\rceil$$ That grows faster than $\frac{1}{2}193^{2^i},$ which grows quite fast. The digits at least double for each sequential $i.$

You can compute $u_{2^i}$ by recursion, noting that $u_{2k}=2u_{k}^2-1.$

The case $i=0$ gives $u_{2^0}=97.$

The case $i=1$ give $u_{2^1}=18817=31\cdot 607$.

The case $i=2$ gives $u_{2^2}=708158977,$ which was found by J.W. Tanner, is prime.

Next, $i=3,$ we have $u_{2^3}=1002978273411373057.$ According to an online checker, this is not prime. (From comments below, it is divisible by $127.$

When $i=4,$ $u_{2^4}=2011930833870518011412817828051050497$ which is not prime.

When $i=5,$ my computation has $$\begin{align}u_{2^5}=8,&095,731,360,557,835,890,888,779,535,060,256,832,\\&479,295,062,749,579,257,164,654,370,487,894,017,\end{align}$$ which is reported as not prime, but I'm not sure I trust the online tool with a number this high.

The only way I know to assert $u_{2^i}$ is prime is to compute and check.

Assuming that the probability that $u_{2^i}$ is prime is random, we'd have that the probability that $u_{2^i}$ is prime is roughly:

$$\frac{2}{2^i\log\left(97+56\sqrt{3}\right)-\log 2}$$

Since the sum of these probabilities is finite, that means we might expect the number of $u_{2^i}$ which are prime could be finite.


That heuristic is slightly weakened because $\gcd(u_{2^i},u_{2^j})=1$ for $i\neq j,$ which makes it more likely that $u_{2^i}$ is prime.

This is because $u_{2^i}=T_{2^i}(97)$ where $T_n$ are the Chebyshev polynomials of the first kind. That means that if $j>i$ then:

$$u_{2^j}=T_{2^j}(97)=T_{2^{j-i}}\left(T_{2^i}(97)\right)=T_{2^{j-i}}(u_{2^i})$$ and $T_{2^{j-i}}$ has constant coefficient $\pm 1,$ so no factor of $u_{2^i}$ is a factor of $u_{2^j}.$

Also, the only prime divisors $p$ of a number of the form $2u^2-1$ are $p\equiv\pm 1\pmod{8}.$ That eliminates approximately half the primes.

If $p\equiv -1\pmod{24}$ then $p$ is never a factor of any $u_{2^i}$ since $3$ is a square modulo $p$ so we have some integers $\alpha=2+\sqrt{3}$ and $\beta=2-\sqrt{3}$ such that $\alpha\beta\equiv 1\pmod{p}$ and $$2u_{2^i}\equiv\alpha^{2^{i+2}}+\beta^{2^{i+2}}\equiv\beta^{2^{i+2}}\left(\alpha^{2^{i+3}}+1\right)\pmod{p}$$ So when $p\equiv -1\pmod{24}$ and $p\mid u_{2^i}$ then $-1$ is a square modulo $p.$ But then $p\equiv 1\pmod 4,$ contradiction.

That removes another $1/4$th of the primes as possible divisors.


For any $p,$ we know that $p\mid u_{2^i}$ only for $i=0,1,\dots,\nu_2(p^2-1)-4.$ That's because the multiplicative group of $\mathbb F_{p^2}$ is cyclic, and $3$ has a square root in $\mathbb F_{p^2},$ so if $-1\equiv \alpha^{2^{i+3}}$ for some $\alpha\in\mathbb F_{p^2},$ then $2^{i+3}\mid \frac{p^2-1}{2}$ or $i+4\leq \nu_{2}(p^2-1).$

So if $p\mid u_{2^k}$ then $\nu_2(p^2-1)\geq k+3.$

You have if $p\equiv 1\pmod{24}$ then $\sqrt{3}$ exists in $\mathbb F_p$ and you now require $\nu_2(p-1)\geq k+3.$

This sort-of explains why some of the initial divisors $(31,127)$ are Mersenne primes $p=2^{q}-1,$ because $\nu_2(p^2-1)=1+q$ is large relative to $p.$

Oddly, the Fermat primes of the form $p=2^{2^n}+1$ are not divisors of any $u_i$ for any of the know $k$ prime cases $n\leq 4.$


You can check any $p$ starting at $w_0=2$ and compute $w_{i+1}= 2w_{i}^2-1\bmod{p}$ until you either get to $0$ or you get to a repeated value.

Using a computer program, I've test all the prime values from $2$ to $1,000,000,000$ to see if they are factors of any $u_{2^i}.$ I've found factors for $i=1,3,4,6,9,10,13,14,15,17.$ These are the $i$ such that $u_{2^i}$ has a factor less than $1,000,000,000.$ I have specific prime divisors $p$ for each of these $i.$

Specifically, if $v_{i}=u_{2^i}$ then:

$$\begin{align}2^5-1=31&\mid v_{1}\\ 2^7-1=127&\mid v_{3}\\ 89\cdot 2^{8}-1=22783&\mid v_{4}\\ 3\cdot 2^{12}+1=12289&\mid v_{6}\\ 2^{13}-1=8191&\mid v_{9}\\3\cdot 151\cdot 2^{16}+1=29687809&\mid v_{10}\\ 2^{17}-1=131071&\mid v_{13}\\ 5\cdot 2^{18}-1=1310719&\mid v_{14}\\ 2^{19}-1=524287&\mid v_{15}\\ 19\cdot 2^{21}-1=39845887&\mid v_{17} \end{align}$$

I also have that $i=5$ does not yield a prime, but no specific factor of $u_{2^5}.$

We know $i=0,i=2$ are primes.

I don't have results for other $i=7,8,11,12,16$ nor $i>17.$


The sequence $w_0=2, w_{n+1}=2w_0^2-1$ turns out to be related to the Lucas–Lehmer primality test for Mersenne numbers. Specifically, in Lucas-Lehmer, $s_n=2w_n.$ This means that, for $q>2,$ $M_q=2^q-1$ is prime if any only if $w_{q-2}$ is divisible by $M_q.$

This explains why $v_{q-4}=w_{q-2}$ is divisible by $M_q$ when $M_q$ is prime, and thus $v_{q-4}$ is not prime when $M_q$ is prime.


another example: $p=708158977$


Addendum:

I did not find this example by continuing the search from $50000000$.

Rather, I solved the Pell equation $p^2-3m^2=1$ as suggested by Thomas Andrews $$\begin{align} &&p &&m &&p \text{ mod } 4\\ && 2 &&1 &&2\\ &&7 &&4 &&3\\ &&26&& 15&& 2\\ &&97&& 56 &&1\\ &&362 &&209&& 2\\ &&1351 &&780 &&3\\ &&5042 &&2911 &&2\\ &&18817 &&10864 &&1\\ &&70226 &&40545 &&2\\ &&262087 &&151316 &&3\\ &&978122 &&564719 &&2\\ &&3650401 &&2107560 &&1\\ &&13623482 &&7865521 &&2\\ &&50843527 &&29354524 &&3\\ &&189750626 &&109552575 &&2\\ &&\color{red}{708158977} &&408855776 &&\color{red}1\\ &&2642885282 &&1525870529 &&2\\ &&9863382151 &&5694626340 &&3\\ &&36810643322 &&21252634831 &&2\\ \end{align}$$ using $p_{n+1}=2p_n+3m_n$ and $m_{n+1}=p_n+2m_n,$

and I looked in the $p$ column for a prime congruent to $1\mod4$.